You are given an array of positive integers nums.
You need to select a subset of nums which satisfies the following condition:
[x, x2, x4, ..., xk/2, xk, xk/2, ..., x4, x2, x] (Note that k can be 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.
Example 1:
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 22 == 4. Hence the answer is 3.
Example 2:
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}, there may be multiple subsets which provide the same answer.
Constraints:
2 <= nums.length <= 1051 <= nums[i] <= 109Problem Overview: You are given an array of integers and must select the largest subset that can be arranged into a symmetric sequence where values follow repeated squaring. A valid structure looks like x, x^2, x^4, ... , x^4, x^2, x. The goal is to maximize the number of elements while respecting the required power relationship between neighbors.
Approach 1: Count Frequency and Form Palindrome (Time: O(n + u log M), Space: O(u))
This approach uses a frequency map to count how often each number appears. For every possible starting value x, repeatedly check whether x, x^2, x^4, and further powers exist using fast hash lookups. Each level of the chain needs at least two occurrences to maintain symmetry on both sides of the sequence. The only exception is the middle element, which can appear once. Handling the value 1 requires special treatment because squaring never changes it, so the answer becomes the largest odd frequency of 1. This method relies heavily on hash table lookups and iterating through unique values in the array.
Approach 2: Using Power Properties (Time: O(n log M), Space: O(u))
This approach focuses on the mathematical property that every next element is the square of the previous one. Build a frequency map, then treat each number as a potential start of a power chain. Repeatedly square the current value and verify its presence in the map. If a value appears at least twice, it can extend the symmetric sequence on both sides. Once a value appears only once, it can act as the center and the chain stops. This method essentially performs controlled enumeration over possible bases while using constant‑time hash lookups to validate each power.
Recommended for interviews: The power‑property approach is what most interviewers expect. It demonstrates that you spotted the repeated squaring pattern and used a hash map to verify the chain efficiently. Showing the frequency-based reasoning first proves you understand the symmetry constraint, but the optimized enumeration of power chains highlights stronger algorithmic insight.
This approach involves finding the occurrences of each number in the array and forming the maximal subset that can be arranged into the palindrome pattern described.
This solution first sorts the array to group identical elements together. It then iterates through the array, counting the number of times each unique number appears. The maximum number of elements we can get is the sum of floor(count/2) for each element (representing a symmetrical position in the pattern) plus one for a central element if needed.
Time Complexity: O(n log n) due to sorting, where n is the number of elements in the array.
Space Complexity: O(1) additional space, as we're only storing counters.
Here we exploit the mathematical properties of powers of 2 to directly compute the maximum subset possible without traversing explicitly looking for subsets.
This implementation exploits powers of 2 by iterating through each element's next possible power. Using the modulus operation, it checks if it divides without remainder. As proper subsets organized by powers assure the best distribution, we check the maximum potential subsets a certain power can create before upgrading to the next.
Time Complexity: O(n log(n)); because we iterate through powers exponentially but within linear element passes.
Space Complexity: O(1) additional space since only counters are used.
We use a hash table cnt to record the occurrence count of each element in the array nums. For each element x, we can keep squaring it until its count in the hash table cnt is less than 2. At this point, we check if the count of x in the hash table cnt is 1. If it is, it means that x can still be included in the subset. Otherwise, we need to remove an element from the subset to ensure the subset count is odd. Then we update the answer and continue to enumerate the next element.
Note that we need to handle the case of x = 1 specially.
The time complexity is O(n times log log M), and the space complexity is O(n). Here, n and M are the length of the array nums and the maximum value in the array nums, respectively.
| Approach | Complexity |
|---|---|
| Count Frequency and Form Palindrome | Time Complexity: O(n log n) due to sorting, where n is the number of elements in the array. |
| Using Power Properties | Time Complexity: O(n log(n)); because we iterate through powers exponentially but within linear element passes. |
| Hash Table + Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Count Frequency and Form Palindrome | O(n + u log M) | O(u) | Good for reasoning about symmetric structure and validating frequency constraints |
| Using Power Properties | O(n log M) | O(u) | Best general solution; leverages repeated squaring pattern with hash lookups |
3020. Find the Maximum Number of Elements in Subset | Why Map & not Unordered Map • Aryan Mittal • 3,430 views views
Watch 9 more video solutions →Practice Find the Maximum Number of Elements in Subset with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor