Find the Maximum Number of Elements in Subset
Problem Description:
You are given an array of positive integers nums.
You need to select a subset of nums which satisfies the following condition:
You can place the selected elements in a 0-indexed array such that it follows the pattern: [x, x², x⁴, ..., xᵏ/², xᵏ, xᵏ/², ..., x⁴, x², x] (Note that k can be any non-negative power of 2).
For example, [2, 4, 16, 4, 2] and [3, 9, 3] follow the pattern while [2, 4, 8, 4, 2] does not.
Return the maximum number of elements in a subset that satisfies these conditions.
Examples:
Input: nums = [5,4,1,2,2]
Output: 3
Explanation: We can select the subset {4,2,2}, which can be placed in the array as [2,4,2] which follows the pattern and 2×2 = 4. Hence the answer is 3.
Input: nums = [1,3,2,4]
Output: 1
Explanation: We can select the subset {1}, which can be placed in the array as [1] which follows the pattern. Hence the answer is 1. Note that we could have also selected the subsets {2}, {3}, or {4}, as there may be multiple subsets which provide the same answer.
Constraints:
2 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
Brute Force Approach:
When we read the problem statement, the first idea that comes to mind is simple:
We need to find the largest subset that follows the pattern [x, x², x⁴, ..., xᵏ/², xᵏ, xᵏ/², ..., x⁴, x², x].
We can observe a few things:
First, except for the largest element xᵏ, every other element in the pattern appears twice. So, the general approach would be to start with an element x and check if it appears at least twice in the array. If it does, we add 2 to the count, then we move on to check its square x².
We repeat this process by continuously checking if the next power of x (like x⁴, x⁸, etc.) is present in the array. If the next power is also found twice, we again add 2 to the count. This continues until we encounter an element that only appears once, which would be our peak element (xᵏ).
If we can't find the next power of x in the array, we know that the last encountered element (which had a frequency of at least 2) should be taken as the peak element, so we decrease the count by 1 (as we only need one of that element, not two).
Now, there's also the special case where the element is 1. If x=1, then 1² = 1, and it will keep repeating, making the pattern go on indefinitely. To handle this, we simply add the frequency of 1 to the count and break out, but if the frequency is even, we need to decrease the count by 1 to ensure the total number of elements is odd (since the pattern always has an odd number of elements due to the peak).
By following this approach, we can build the largest valid subset and return the maximum count.
Let's understand with an example:
Input: nums = [5, 4, 1, 2, 2]
Step-by-Step Execution:
Initialize Variables:
maxSize = 1 (start with a minimum size for the subset).
Iterate over each unique element in the array:
Processing element 5:
- Frequency of 5 = 1 (appears 1 time).
- Since the frequency of 5 is 1, it is the peak, so we add 1 to the count:
- count = 1
- Update maxSize:
- maxSize = max(1, 1) = 1
Processing element 4:
- Frequency of 4 = 1 (appears 1 time).
- Since the frequency of 4 is 1, it is the peak, so we add 1 to the count:
- count = 1
- Update maxSize:
- maxSize = max(1, 1) = 1
Processing element 1:
- Frequency of 1 = 1 (appears 1 time).
- Since the frequency of 1 is 1, it is the peak, so we add 1 to the count:
- count = 1
- Update maxSize:
- maxSize = max(1, 1) = 1
Processing element 2:
- Frequency of 2 = 2 (appears 2 times).
- Since the frequency of 2 is even, add 2 to the count and check for 2² = 4.
- 4 is present with frequency 1, so add 1 to the count and break:
- count = 3
- Update maxSize:
- maxSize = max(1, 3) = 3
Processing element 2 (again):
- Frequency of 2 = 2 (already processed).
- This has already been handled, so we skip further steps for this.
Final Result: maxSize = 3
How to code it up?
Here are the steps to code it up:
- Initialize Variables:
- maxSize: Variable to track the maximum subset size. Initialize it to 1.
- Iterate Over Elements:
- For each element x in nums, follow the next steps.
- Count Frequency of x:
- Use a loop to count how many times x appears in nums.
- Handle the Special Case for x = 1:
- If x == 1, add its frequency to count and break the loop because it will infinitely repeat in the pattern.
- Handle Elements with Frequency >= 2:
- If the frequency of x is greater than or equal to 2, add 2 to count.
- Check for the next power of x (i.e., x², x⁴, etc.). If found, continue checking powers of x (multiply x by itself).
- Handle Single Occurrence (freq == 1):
- If the frequency of x is exactly 1, treat it as the peak element (xᵏ). Add 1 to count and break the loop.
- Adjust count:
- If count is even, subtract 1 to ensure the number of elements in the subset is odd (due to the peak element).
- Update maxSize:
- After processing each element, update maxSize to be the maximum of its current value and the current count.
- Return Result:
- After iterating through all elements, return maxSize.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
// Function to find the maximum length of a valid subset following the pattern
int maximumLength(vector<int>& nums) {
// Initialize the size of the array
int n = nums.size();
// Variable to store the maximum size of the valid subset
long long maxSize = 1;
// Iterate over each element in the array
for (int i = 0; i < nums.size(); i++) {
// Store the current element
long long x = nums[i];
// Initialize the count of valid elements for the current x
long long count = 0;
// Start an infinite loop to check the powers of x
while(true)
{
// Variable to store the frequency of the current element x in the array
int freq = 0;
// Loop through the entire array to count the frequency of x
for(int i=0; i<n; i++)
{
if(nums[i] == x)
freq++;
}
// Special case: If x is 1, it will continue to appear as 1², 1⁴, etc.
if(x == 1)
{
// Add the frequency of 1 to count, as it will follow the pattern
count += freq;
break;
}
// If the frequency of x is greater than or equal to 2
if(freq >= 2)
{
// Add 2 to the count (as x appears at least twice in the pattern)
count += 2;
// Move to the next power of x (x², x⁴, etc.)
x *= x;
}
// If the frequency of x is exactly 1, we've found the peak element
else if(freq == 1)
{
// Add 1 to count for the peak element (xᵏ)
count++;
break;
}
// If x doesn't exist in the array, break the loop
else
break;
}
// If count is even, subtract 1 to ensure an odd-length subset
if(count % 2 == 0)
count--;
// Update the maximum size of the valid subset
maxSize = max(maxSize, count);
}
// Return the maximum valid subset size
return maxSize;
}
};
2. Java Try on Compiler
class Solution {
public int maximumLength(int[] nums) {
// Initialize the size of the array
int n = nums.length;
// Variable to store the maximum size of the valid subset
long maxSize = 1;
// Iterate over each element in the array
for (int i = 0; i < nums.length; i++) {
// Store the current element
long x = nums[i];
// Initialize the count of valid elements for the current x
long count = 0;
// Start an infinite loop to check the powers of x
while (true) {
// Variable to store the frequency of the current element x in the array
int freq = 0;
// Loop through the entire array to count the frequency of x
for (int j = 0; j < n; j++) {
if (nums[j] == x) {
freq++;
}
}
// Special case: If x is 1, it will continue to appear as 1², 1⁴, etc.
if (x == 1) {
// Add the frequency of 1 to count, as it will follow the pattern
count += freq;
break;
}
// If the frequency of x is greater than or equal to 2
if (freq >= 2) {
// Add 2 to the count (as x appears at least twice in the pattern)
count += 2;
// Move to the next power of x (x², x⁴, etc.)
x *= x;
}
// If the frequency of x is exactly 1, we've found the peak element
else if (freq == 1) {
// Add 1 to count for the peak element (xᵏ)
count++;
break;
}
// If x doesn't exist in the array, break the loop
else {
break;
}
}
// If count is even, subtract 1 to ensure an odd-length subset
if (count % 2 == 0) {
count--;
}
// Update the maximum size of the valid subset
maxSize = Math.max(maxSize, count);
}
// Return the maximum valid subset size
return (int) maxSize;
}
}
3. Python Try on Compiler
class Solution:
def maximumLength(self, nums):
# Initialize the size of the array
n = len(nums)
# Variable to store the maximum size of the valid subset
maxSize = 1
# Iterate over each element in the array
for i in range(len(nums)):
# Store the current element
x = nums[i]
# Initialize the count of valid elements for the current x
count = 0
# Start an infinite loop to check the powers of x
while True:
# Variable to store the frequency of the current element x in the array
freq = 0
# Loop through the entire array to count the frequency of x
for num in nums:
if num == x:
freq += 1
# Special case: If x is 1, it will continue to appear as 1², 1⁴, etc.
if x == 1:
# Add the frequency of 1 to count, as it will follow the pattern
count += freq
break
# If the frequency of x is greater than or equal to 2
if freq >= 2:
# Add 2 to the count (as x appears at least twice in the pattern)
count += 2
# Move to the next power of x (x², x⁴, etc.)
x *= x
# If the frequency of x is exactly 1, we've found the peak element
elif freq == 1:
# Add 1 to count for the peak element (xᵏ)
count += 1
break
# If x doesn't exist in the array, break the loop
else:
break
# If count is even, subtract 1 to ensure an odd-length subset
if count % 2 == 0:
count -= 1
# Update the maximum size of the valid subset
maxSize = max(maxSize, count)
# Return the maximum valid subset size
return maxSize
4. Javascript Try on Compiler
/**
* @param {number[]} nums
* @return {number}
*/
var maximumLength = function (nums) {
// Initialize the size of the array
const n = nums.length;
// Variable to store the maximum size of the valid subset
let maxSize = 1;
// Iterate over each element in the array
for (let i = 0; i < nums.length; i++) {
// Store the current element
let x = nums[i];
// Initialize the count of valid elements for the current x
let count = 0;
// Start an infinite loop to check the powers of x
while (true) {
// Variable to store the frequency of the current element x in the array
let freq = 0;
// Loop through the entire array to count the frequency of x
for (let j = 0; j < n; j++) {
if (nums[j] === x) {
freq++;
}
}
// Special case: If x is 1, it will continue to appear as 1², 1⁴, etc.
if (x === 1) {
// Add the frequency of 1 to count, as it will follow the pattern
count += freq;
break;
}
// If the frequency of x is greater than or equal to 2
if (freq >= 2) {
// Add 2 to the count (as x appears at least twice in the pattern)
count += 2;
// Move to the next power of x (x², x⁴, etc.)
x *= x;
}
// If the frequency of x is exactly 1, we've found the peak element
else if (freq === 1) {
// Add 1 to count for the peak element (xᵏ)
count++;
break;
}
// If x doesn't exist in the array, break the loop
else {
break;
}
}
// If count is even, subtract 1 to ensure an odd-length subset
if (count % 2 === 0) {
count--;
}
// Update the maximum size of the valid subset
maxSize = Math.max(maxSize, count);
}
// Return the maximum valid subset size
return maxSize;
};
Time Complexity: O(n² ⋅ log( max ( nums )))
The for loop iterates through all elements of the array nums. Let the size of the array be n. Thus, this loop runs O(n) times.
For each element nums[i], the while (true) loop checks powers of x (x, x², x⁴, ...). The loop continues until:
- x no longer exists in the array, or
- x is 1, or
- The frequency conditions are met.
In the worst case:
The while loop iterates until the powers of x exceed the largest value in the array.
If x is small (e.g., x = 2), the number of iterations depends on how many times you can square x before it exceeds the range of values in the array.
Number of iterations per while loop: This depends on the largest power of x within the range of array values. In practice, it can be considered logarithmic relative to the size of nums (if we assume that array values grow exponentially due to squaring). Thus, this loop is approximately O(log(max(nums))).
Inside the while loop, there is a for loop that iterates through the entire array nums to count the frequency of the current x. This loop runs O(n) times.
Total Time Complexity
For each element in the outer loop (O(n)), the while loop runs approximately O(log(max(nums))), and within each iteration of the while loop, the frequency count loop runs O(n). Thus, the total time complexity is: O(n) × O(log(max(nums))×n) = O(n² ⋅ log( max ( nums )))
Space Complexity: O(n)
Auxiliary Space Complexity: O(1)
Explanation: The given algorithm uses only a few extra variables for computation, such as maxSize, count, x, and freq. These are scalar values and do not depend on the size of the input.
No additional data structures (e.g., arrays, hashmaps, etc.) are used.
Thus, the auxiliary space complexity is O(1).
Total Space Complexity: O(n)
Explanation: The total space complexity includes both:
The space used by the input array nums.
The auxiliary space used for computation.
The input array nums occupies O(n) space, where n is the number of elements in the array. The auxiliary space complexity is O(1), as calculated above.
Thus, the total space complexity is: O(n) + O(1) = O(n)
Will Brute Force Work Against the Given Constraints?
The current solution has a time complexity of O(n² ⋅ log( max ( nums ))). This is not suitable for n ≤ 10⁵, as the number of operations for the worst-case scenario would be approximately 10¹⁰ (for n = 10⁵).
In competitive programming environments, solutions must generally handle up to 10⁶ operations per test case efficiently. However, the current approach far exceeds this threshold for larger input sizes, leading to Time Limit Exceeded (TLE) errors.
For example, if n = 10⁵, the solution performs O(n² ⋅ log(max(nums))) operations, which results in a minimum of 10¹⁰ operations for a single test case, considering only the n² factor. When multiple test cases are involved, the total number of operations could grow significantly, exacerbating the performance issue.
Additionally, given that the values in the array can be as large as 10⁹, the frequent squaring of numbers in the while loop further increases the computational burden, especially as the range of values becomes extensive.
Thus, for the given constraints, this solution is not efficient and is unlikely to meet the time limits for competitive programming problems with larger input sizes or numerous test cases.
Can we optimize it?
Yes, of course!
We can definitely optimize it—let's do it!
In the previous approach, we traversed through every element and checked if we could form the pattern starting from that element by searching through the entire array to find its pair. If a pair was found, we continued to find its square and so on. This collectively resulted in O(n² ⋅ log(max(nums))) time, which is inefficient.
Now, the question is: how can we optimize this?
Observe that for each element, we are searching whether it exists in the array or not and counting its frequency. This operation alone takes O(n) time for each element, which collectively pushes the overall time complexity beyond O(n²).
Can we optimize this part?
Think about it: what if we had a faster lookup mechanism?
Yes! We can use hashing to speed up the lookup process.
To be specific, let's use a hashmap.
Why not a Hashtable?
Well, the constraints are high here, as nums[i] can go up to 10⁹. Using a hashtable would lead to huge memory consumption and wastage.
So, a hashmap is the ideal choice!
What are hashmap's?
Hash maps are a powerful data structure that store key-value pairs, allowing for fast access to values using their keys. They are used to determine where to store each pair, enabling average-case time complexities of O(1) for insertion, search, and deletion.
Now, the approach would be as follows:
First, store all the elements of nums in a hashmap along with their frequencies.
Then, for every element, maintain a count to track the size of the subset. Start by checking its frequency:
- If the element is 1, simply add its frequency to the count (since 1 repeats as 1², 1⁴, and so on) and break.
- Otherwise, check if the frequency is greater than or equal to 2. If yes, increase the count by 2, then check for its square (e.g., x → x² → x⁴) and continue this process.
- If the frequency of the current element becomes 1, it means we’ve reached the peak element, so increase the count by 1 and break.
- If the element’s square is not found in the hashmap, it means the current element is the peak.
Finally, if the count is even at the end of this process, reduce it by 1 because the pattern can only contain an odd number of values, and in such cases, the last value serves as the peak element.
This ensures we correctly identify the largest subset that follows the desired pattern!
Here's a slight optimization: Since we are checking the square of the current element if the conditions are fulfilled, and nums[i] can only range up to 10⁹, we can stop early for efficiency.
If the current value exceeds 10⁵, squaring it would result in a value 10¹⁰, which is greater than 10⁹, which would not exist in the array nums. So, in such cases, we can simply break the loop and avoid unnecessary calculations.
This small adjustment helps optimize the approach by preventing unnecessary checks for values that are guaranteed to be out of bounds.
Let's understand with an example:
Let' take an array, nums = [5, 4, 1, 2, 2]
Step 1: Create a hashmap with frequencies
- mp = {5: 1, 4: 1, 1: 1, 2: 2}
Step 2: Iterate over each number and calculate the count
Iteration 1: number = 5
- num = 5, freq = 1
- cnt = 1 (since freq == 1)
- ans = max(1, 1) = 1
Iteration 2: number = 4
- num = 4, freq = 1
- cnt = 1 (since freq == 1)
- ans = max(1, 1) = 1
Iteration 3: number = 1
- num = 1, freq = 1
- cnt = 2 (since num == 1, add frequency of 1)
- Adjust cnt = 1 (since cnt is even)
- ans = max(1, 1) = 1
Iteration 4: number = 2
- num = 2, freq = 2
- cnt = 2 (since freq >= 2)
- Move to num = 4 (2² = 4), freq = 1, add 1 to cnt.
- cnt = 3
- ans = max(1, 3) = 3
Iteration 5: number = 2 (duplicate)
- No change, ans = 3
Final Result: The maximum length of the subset is 3.
How to code it up:
Here are the steps to code it up:
- Initialize a hashmap to store the frequency of each element in the nums array.
- Count the frequencies of each element in nums using the hashmap.
- Iterate through each element in the nums array and:
- Start with the current element num.
- Get its frequency from the hashmap.
- Initialize a count variable for the valid subset.
- Process each element:
- If num is 1, add its frequency to count and break (since it will follow the pattern indefinitely).
- If the frequency of num is 2 or more, add 2 to count (as it appears twice in the pattern).
- If the frequency of num is 1, add 1 to count (this is the peak element).
- If num > 10⁵, break the loop to avoid exceeding bounds for squares.
- Ensure the count is odd: If count is even, subtract 1 (as the pattern must have an odd number of elements).
- Update the maximum length of the valid subset with the max of count and the current maxSize.
- Return the final result which is the maximum length of the valid subset.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
// Function to find the maximum length of a valid subset following the pattern
int maximumLength(vector<int>& nums) {
// Create a hashmap to store the frequency of each element in nums
unordered_map<int, int> mp;
// Initialize the answer to 1 (minimum subset size)
int ans = 1;
// Populate the hashmap with the frequency of each number in the array
for(auto &num: nums)
{
mp[num]++;
}
// Iterate through each number in the array
for(auto &number: nums)
{
// Store the current number
long long num = number;
// Get the frequency of the current number from the hashmap
int freq = mp[num];
// Initialize a counter to track the size of the valid subset
int cnt = 0;
// Start checking powers of the current number in the pattern
while(mp.find(num) != mp.end())
{
// Special case: If the number is 1, handle it separately
if(num == 1){
// Add the frequency of 1 to the count and break
cnt += mp[1];
break;
}
// If the frequency of the number is greater than or equal to 2
else if(mp[num] >= 2)
// Add 2 to the count (since the number appears at least twice)
cnt += 2;
// If the frequency of the number is 1 (this is the peak element)
else if(mp[num] == 1)
{
// Add 1 to the count and break (found the peak element)
cnt ++;
break;
}
// If the number exceeds 10⁵, break the loop as it will result in a value greater than 10⁹
if(num > 1e5)
break;
// Move to the next power of the current number (num², num⁴, etc.)
num *= num;
}
// If count is even, subtract 1 to ensure the length is odd
if(cnt%2 == 0)
cnt--;
// Update the maximum length of the valid subset
ans = max(ans, cnt);
}
// Return the final maximum length of the valid subset
return ans;
}
};
2. Java Try on Compiler
class Solution {
public int maximumLength(int[] nums) {
Map<Integer, Integer> mp = new HashMap<>();
// Initialize the maximum length of a valid subset to 1
int ans = 1;
// Calculate the frequency of each number in the array
for (int num : nums) {
mp.put(num, mp.getOrDefault(num, 0) + 1);
}
// Iterate through each number in the array
for (int num : nums) {
int cnt = 0; // Initialize count of numbers in the current subset
long current = num;
// Iterate through powers of the current number
while (mp.containsKey((int)current)) {
// If the current number is 1, add its frequency and break
if (current == 1) {
cnt += mp.get(1);
break;
}
// If the current number appears at least twice
else if (mp.get((int)current) >= 2) {
cnt += 2;
}
// If the current number appears only once (peak element)
else if (mp.get((int)current) == 1) {
cnt += 1;
break;
}
// Avoid overflow by breaking if current exceeds 10^5
if (current > 100000) {
break;
}
// Calculate the next power of the current number
current *= current;
}
// Ensure the subset size is odd
if (cnt % 2 == 0) {
cnt--;
}
// Update the maximum length if necessary
ans = Math.max(ans, cnt);
}
return ans;
}
}3. Python Try on Compiler
class Solution:
def maximumLength(self, nums):
# Create a hashmap to store the frequency of each element in nums
mp = {}
# Initialize the answer to 1 (minimum subset size)
ans = 1
# Populate the hashmap with the frequency of each number in the array
for num in nums:
mp[num] = mp.get(num, 0) + 1
# Iterate through each number in the array
for number in nums:
# Store the current number
num = number
# Get the frequency of the current number from the hashmap
freq = mp[num]
# Initialize a counter to track the size of the valid subset
cnt = 0
# Start checking powers of the current number in the pattern
while num in mp:
# Special case: If the number is 1, handle it separately
if num == 1:
# Add the frequency of 1 to the count and break
cnt += mp[1]
break
# If the frequency of the number is greater than or equal to 2
elif mp[num] >= 2:
# Add 2 to the count (since the number appears at least twice)
cnt += 2
# If the frequency of the number is 1 (this is the peak element)
elif mp[num] == 1:
# Add 1 to the count and break (found the peak element)
cnt += 1
break
# If the number exceeds 10⁵, break the loop as it will result in a value greater than 10⁹
if num > 1e5:
break
# Move to the next power of the current number (num², num⁴, etc.)
num *= num
# If count is even, subtract 1 to ensure the length is odd
if cnt % 2 == 0:
cnt -= 1
# Update the maximum length of the valid subset
ans = max(ans, cnt)
# Return the final maximum length of the valid subset
return ans
4. Javascript Try on Compiler
/**
* @param {number[]} nums
* @return {number}
*/
var maximumLength = function (nums) {
// Create a hashmap to store the frequency of each element in nums
let mp = new Map();
// Initialize the answer to 1 (minimum subset size)
let ans = 1;
// Populate the hashmap with the frequency of each number in the array
for (let num of nums) {
mp.set(num, (mp.get(num) || 0) + 1);
}
// Iterate through each number in the array
for (let number of nums) {
// Store the current number
let num = number;
// Get the frequency of the current number from the hashmap
let freq = mp.get(num);
// Initialize a counter to track the size of the valid subset
let cnt = 0;
// Start checking powers of the current number in the pattern
while (mp.has(num)) {
// Special case: If the number is 1, handle it separately
if (num === 1) {
// Add the frequency of 1 to the count and break
cnt += mp.get(1);
break;
}
// If the frequency of the number is greater than or equal to 2
else if (mp.get(num) >= 2) {
// Add 2 to the count (since the number appears at least twice)
cnt += 2;
}
// If the frequency of the number is 1 (this is the peak element)
else if (mp.get(num) === 1) {
// Add 1 to the count and break (found the peak element)
cnt += 1;
break;
}
// If the number exceeds 10⁵, break the loop as it will result in a value greater than 10⁹
if (num > 1e5) {
break;
}
// Move to the next power of the current number (num², num⁴, etc.)
num *= num;
}
// If count is even, subtract 1 to ensure the length is odd
if (cnt % 2 === 0) {
cnt -= 1;
}
// Update the maximum length of the valid subset
ans = Math.max(ans, cnt);
}
// Return the final maximum length of the valid subset
return ans;
};
Time Complexity: O(n * log(log(max(nums))))
The time complexity of the approach can be broken down into several steps:
- Building the frequency hashmap: We iterate through the array once to populate the hashmap with the frequency of each element. This takes O(n) time, where n is the size of the input array.
- Iterating over each element in the array: Inside the
whileloop, we: - Loop over each element in the array to check if we can form the pattern starting from that element.
- For each element, we perform a series of checks and operations in the while loop.
- Check if the current number exists in the hashmap: This operation is O(1), as we are using a hashmap.
- Check the frequency of the number: This operation is also O(1), since we are using a hashmap.
- Update the number to its square and check again if it exists in the hashmap: We repeat this process, but break the loop if the number exceeds 10⁵ (because any value larger than 10⁵ will lead to a number greater than 10⁹, which is outside the bounds of the input).
For each iteration of the while loop, the number grows exponentially (from x to x², x⁴, etc.). The number of iterations is limited by 10⁵, and after k iterations, the number will be x²ˣ.
To determine when it exceeds 10⁵, we solve for k:
- x²ˣ ≤ 10⁵
Taking the logarithm (base 10) of both sides:
- 2ˣ * log(x) ≤ log(10⁵)
- 2ˣ ≤ log(10⁵) / log(x)
Thus, the number of iterations k is proportional to log(log(max(nums))), since log(10⁵) is constant and log(x) depends on the element x. Therefore, the time complexity of the while loop is O(log(log(max(nums)))).
Overall Complexity: For each element in the array, the while loop runs at most O(log(log(max(nums)))) times. Thus, for n elements in the array, the overall time complexity is O(n * log(log(max(nums)))).
Final Time Complexity: O(n * log(log(max(nums)))).
Space Complexity: O(n)
- Auxiliary Space Complexity: O(n)
Explanation: We store the frequency of each number in the input array, which requires O(n) space, where n is the size of the array. We use a constant amount of extra space for variables such as cnt, num, and freq. These require O(1) space.
Thus, the auxiliary space complexity is O(n) because the hashmap stores up to n elements. - Total Space Complexity: O(n)
Explanation: The input array nums itself requires O(n) space. The hashmap requires O(n) space for storing frequencies. The other variables consume O(1) space.
Therefore, the total space complexity is O(n), accounting for both the input array and the space used by the hashmap.
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
1. Word Subsets
You are given two lists of words: words1 and words2.
A word from words2 is called a subset of a word in words1 if:All the letters in the word from words2 are present in the word from words1.
And each letter appears at least as many times in the word from words1 as it does in the word from words2.For example:
"wrr" is a subset of "warrior" (because "warrior" has at least 2 'r's and one 'w').
But "wrr" is not a subset of "world" (because "world" doesn’t have 2 'r's).A word from words1 is called universal if:
Every word in words2 is a subset of it.The goal is to return all the universal words from words1.
You are given an array of strings of the same length words.
In one move, you can swap any two even indexed characters or any two odd indexed characters of a string words[i].
Two strings words[i] and words[j] are special-equivalent if after any number of moves, words[i] == words[j].For example, words[i] = "zzxy" and words[j] = "xyzz" are special-equivalent because we may make the moves "zzxy" -> "xzzy" -> "xyzz".
A group of special-equivalent strings from words is a non-empty subset of words such that:
1. Every pair of strings in the group are special equivalent, and
2. The group is the largest size possible (i.e., there is not a string words[i] not in the group such that words[i] is special-equivalent to every string in the group).Return the number of groups of special-equivalent strings from words.