Watch 10 video solutions for Find the Maximum Number of Elements in Subset, a medium level problem involving Array, Hash Table, Enumeration. This walkthrough by Aryan Mittal has 3,430 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |