Find the Maximum Number of Elements in Subset

Med

#2688Time: O(U * (log M)^2), where `U` is the number of unique elements in `nums` and `M` is the maximum value in `nums`. For each of the `U` unique numbers as a potential base, we have an outer loop for `p` which runs up to `log2(log_x(M))` times. Inside it, another loop checks previous powers, running `p` times. This gives a complexity roughly proportional to `(log M)^2` for each base.Space: O(U), for storing the frequency map.

Patterns

Enumeration

Data structures

Array Hash Table

Prompt

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^k/2, x^k, x^k/2, ..., x⁴, x², 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 <= 10⁵
1 <= nums[i] <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

A straightforward approach is to consider every unique number in the input array nums as a potential base x for the special pattern. For each potential base x, we can then determine the longest possible valid pattern that can be formed.

Algorithm

Algorithm:
1. Create a frequency map (e.g., a HashMap) of all numbers in nums.
2. Handle the special case for the number 1. If there are c ones, the maximum subset size we can form is c if c is odd, and c-1 if c is even and positive. Initialize the overall maximum length with this value, or with 1 if no ones exist but the array is non-empty.
3. Iterate through each unique number x from the frequency map (where x > 1).
4. For each x, we try to build the longest possible pattern by checking for increasing powers of 2 in the exponent: p = 0, 1, 2, ....
5. For a given p, the pattern's peak is x^(2^p) and its length is 2*p + 1. This requires one x^(2^p) and two of each x^(2^i) for 0 <= i < p.
6. We check if the frequency map has sufficient counts for each required element. We find the maximum p that satisfies the conditions for base x.
7. The length of the subset for this p is 2*p + 1. We update our overall maximum length with the largest one found across all possible bases x.
Code Snippet:

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int maximumLength(int[] nums) {6        Map<Long, Integer> counts = new HashMap<>();7        for (int num : nums) {8            counts.put((long)num, counts.getOrDefault((long)num, 0) + 1);9        }10 11        int maxLen = 0;12        int countOfOnes = counts.getOrDefault(1L, 0);13        if (countOfOnes > 0) {14            maxLen = (countOfOnes % 2 == 1) ? countOfOnes : countOfOnes - 1;15        }16        // Any single element can form a subset of size 117        if (nums.length > 0) {18             maxLen = Math.max(maxLen, 1);19        }20 21        for (long x : counts.keySet()) {22            if (x == 1) continue;23 24            // Check for chains starting with x25            long currentNum = x;26            int p = 0;27            while (true) {28                // Check if pattern with peak x^(2^p) is possible29                boolean possible = true;30                long peak = currentNum;31                if (counts.getOrDefault(peak, 0) < 1) {32                    possible = false;33                }34 35                long tempNum = x;36                for (int i = 0; i < p; i++) {37                    if (counts.getOrDefault(tempNum, 0) < 2) {38                        possible = false;39                        break;40                    }41                    tempNum = tempNum * tempNum;42                }43 44                if (possible) {45                    maxLen = Math.max(maxLen, 2 * p + 1);46                    long nextNum = currentNum * currentNum;47                    if (nextNum > 1_000_000_000L) break;48                    currentNum = nextNum;49                    p++;50                } else {51                    break;52                }53            }54        }55 56        return maxLen;57    }58}

Walkthrough

The core idea is to first count the frequency of each number in nums. Then, for each unique number x > 1, we check how long of a geometric progression x, x^2, x^4, ... we can form based on the available counts.

Algorithm:
1. Create a frequency map (e.g., a HashMap) of all numbers in nums.
2. Handle the special case for the number 1. If there are c ones, the maximum subset size we can form is c if c is odd, and c-1 if c is even and positive. Initialize the overall maximum length with this value, or with 1 if no ones exist but the array is non-empty.
3. Iterate through each unique number x from the frequency map (where x > 1).
4. For each x, we try to build the longest possible pattern by checking for increasing powers of 2 in the exponent: p = 0, 1, 2, ....
5. For a given p, the pattern's peak is x^(2^p) and its length is 2*p + 1. This requires one x^(2^p) and two of each x^(2^i) for 0 <= i < p.
6. We check if the frequency map has sufficient counts for each required element. We find the maximum p that satisfies the conditions for base x.
7. The length of the subset for this p is 2*p + 1. We update our overall maximum length with the largest one found across all possible bases x.
Code Snippet:

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int maximumLength(int[] nums) {6        Map<Long, Integer> counts = new HashMap<>();7        for (int num : nums) {8            counts.put((long)num, counts.getOrDefault((long)num, 0) + 1);9        }10 11        int maxLen = 0;12        int countOfOnes = counts.getOrDefault(1L, 0);13        if (countOfOnes > 0) {14            maxLen = (countOfOnes % 2 == 1) ? countOfOnes : countOfOnes - 1;15        }16        // Any single element can form a subset of size 117        if (nums.length > 0) {18             maxLen = Math.max(maxLen, 1);19        }20 21        for (long x : counts.keySet()) {22            if (x == 1) continue;23 24            // Check for chains starting with x25            long currentNum = x;26            int p = 0;27            while (true) {28                // Check if pattern with peak x^(2^p) is possible29                boolean possible = true;30                long peak = currentNum;31                if (counts.getOrDefault(peak, 0) < 1) {32                    possible = false;33                }34 35                long tempNum = x;36                for (int i = 0; i < p; i++) {37                    if (counts.getOrDefault(tempNum, 0) < 2) {38                        possible = false;39                        break;40                    }41                    tempNum = tempNum * tempNum;42                }43 44                if (possible) {45                    maxLen = Math.max(maxLen, 2 * p + 1);46                    long nextNum = currentNum * currentNum;47                    if (nextNum > 1_000_000_000L) break;48                    currentNum = nextNum;49                    p++;50                } else {51                    break;52                }53            }54        }55 56        return maxLen;57    }58}

Complexity

Time

O(U * (log M)^2), where `U` is the number of unique elements in `nums` and `M` is the maximum value in `nums`. For each of the `U` unique numbers as a potential base, we have an outer loop for `p` which runs up to `log2(log_x(M))` times. Inside it, another loop checks previous powers, running `p` times. This gives a complexity roughly proportional to `(log M)^2` for each base.

Space

O(U), for storing the frequency map.

Trade-offs

Pros

Conceptually simple and directly follows the problem definition.
Guaranteed to find the correct answer by exhaustively checking all possibilities for bases.

Cons

Inefficient due to redundant computations. For example, a chain starting with base 4 will be re-evaluated even if a chain starting with base 2 (which contains 4) has already been processed.
The nested loops make it slow for large ranges of numbers, although the rapid growth of x^(2^p) keeps it from being prohibitively slow.

This approach improves upon the previous one by avoiding redundant computations. We still use a frequency map, but we ensure that each potential geometric progression (x, x^2, x^4, ...) is processed only once. We can achieve this by keeping track of numbers that have already been considered as part of a longer chain.

Algorithm

Algorithm:
1. Count the frequencies of all numbers and store them in a map.
2. Initialize maxLen. Handle the special case of the number 1 as before. The minimum answer is 1 if the array is not empty.
3. Create a visited set to store numbers that have already been part of a chain calculation.
4. Iterate through each unique number num from the frequency map.
5. If num is 1 or has been visited, skip it.
6. A number num can only serve as a non-peak element in the pattern if its count is at least 2. If count[num] < 2, it cannot be the base of a symmetric pattern, so we skip it. (The case [num] is already covered by maxLen initialization).
7. If count[num] >= 2, we start building a chain: num, num^2, num^4, ....
8. Initialize the current subset length to 1 (for the pattern [num]).
9. In a loop, calculate the next term next_val = current_num^2. Mark next_val as visited.
10. If next_val exists in our frequency map:
  - If count[next_val] >= 2, we can extend the symmetric part of our pattern. Add 2 to the current length.
  - If count[next_val] == 1, this number must be the peak. We add 2 to the length and terminate the chain building for this base.
11. If next_val does not exist, the chain ends.
12. Update the overall maxLen with the length found for the current chain.
Code Snippet:

1import java.util.HashMap;2import java.util.HashSet;3import java.util.Map;4import java.util.Set;5 6class Solution {7    public int maximumLength(int[] nums) {8        Map<Long, Integer> counts = new HashMap<>();9        boolean hasElements = nums.length > 0;10        for (int num : nums) {11            counts.put((long)num, counts.getOrDefault((long)num, 0) + 1);12        }13 14        int maxLen = 0;15        int countOfOnes = counts.getOrDefault(1L, 0);16        if (countOfOnes > 0) {17            maxLen = (countOfOnes % 2 == 1) ? countOfOnes : countOfOnes - 1;18        }19        if (hasElements) {20            maxLen = Math.max(maxLen, 1);21        }22 23        Set<Long> visited = new HashSet<>();24 25        for (long num : counts.keySet()) {26            if (num == 1 || visited.contains(num)) {27                continue;28            }29 30            if (counts.get(num) < 2) {31                continue;32            }33 34            int currentLen = 1;35            long currentNum = num;36            visited.add(currentNum);37 38            while (true) {39                long nextNum = currentNum * currentNum;40                if (nextNum > 1_000_000_000L) {41                    break;42                }43                visited.add(nextNum);44                if (!counts.containsKey(nextNum)) {45                    break;46                }47 48                if (counts.get(nextNum) >= 2) {49                    currentLen += 2;50                } else { // count == 151                    currentLen += 2;52                    break;53                }54                currentNum = nextNum;55            }56            maxLen = Math.max(maxLen, currentLen);57        }58 59        return maxLen;60    }61}

Walkthrough

The key insight is that if we have a chain starting with x, any chain starting with x^2, x^4, etc., will be shorter or equal in length. Therefore, we only need to start checking from the smallest possible base of a chain. We can use a visited set to mark numbers that have been processed.

Algorithm:
1. Count the frequencies of all numbers and store them in a map.
2. Initialize maxLen. Handle the special case of the number 1 as before. The minimum answer is 1 if the array is not empty.
3. Create a visited set to store numbers that have already been part of a chain calculation.
4. Iterate through each unique number num from the frequency map.
5. If num is 1 or has been visited, skip it.
6. A number num can only serve as a non-peak element in the pattern if its count is at least 2. If count[num] < 2, it cannot be the base of a symmetric pattern, so we skip it. (The case [num] is already covered by maxLen initialization).
7. If count[num] >= 2, we start building a chain: num, num^2, num^4, ....
8. Initialize the current subset length to 1 (for the pattern [num]).
9. In a loop, calculate the next term next_val = current_num^2. Mark next_val as visited.
10. If next_val exists in our frequency map:
  - If count[next_val] >= 2, we can extend the symmetric part of our pattern. Add 2 to the current length.
  - If count[next_val] == 1, this number must be the peak. We add 2 to the length and terminate the chain building for this base.
11. If next_val does not exist, the chain ends.
12. Update the overall maxLen with the length found for the current chain.
Code Snippet:

1import java.util.HashMap;2import java.util.HashSet;3import java.util.Map;4import java.util.Set;5 6class Solution {7    public int maximumLength(int[] nums) {8        Map<Long, Integer> counts = new HashMap<>();9        boolean hasElements = nums.length > 0;10        for (int num : nums) {11            counts.put((long)num, counts.getOrDefault((long)num, 0) + 1);12        }13 14        int maxLen = 0;15        int countOfOnes = counts.getOrDefault(1L, 0);16        if (countOfOnes > 0) {17            maxLen = (countOfOnes % 2 == 1) ? countOfOnes : countOfOnes - 1;18        }19        if (hasElements) {20            maxLen = Math.max(maxLen, 1);21        }22 23        Set<Long> visited = new HashSet<>();24 25        for (long num : counts.keySet()) {26            if (num == 1 || visited.contains(num)) {27                continue;28            }29 30            if (counts.get(num) < 2) {31                continue;32            }33 34            int currentLen = 1;35            long currentNum = num;36            visited.add(currentNum);37 38            while (true) {39                long nextNum = currentNum * currentNum;40                if (nextNum > 1_000_000_000L) {41                    break;42                }43                visited.add(nextNum);44                if (!counts.containsKey(nextNum)) {45                    break;46                }47 48                if (counts.get(nextNum) >= 2) {49                    currentLen += 2;50                } else { // count == 151                    currentLen += 2;52                    break;53                }54                currentNum = nextNum;55            }56            maxLen = Math.max(maxLen, currentLen);57        }58 59        return maxLen;60    }61}

Complexity

Time

O(N + U * log M), where `N` is the length of `nums`, `U` is the number of unique elements, and `M` is the maximum value. `O(N)` is for building the frequency map. The main loop iterates up to `U` times. The inner `while` loop for a number `x` involves repeated squaring, so it runs at most `log(M)` times. Since we use a `visited` set, each chain is processed only once.

Space

O(U), for the frequency map and the `visited` set.

Trade-offs

Pros

Highly efficient due to memoization (using the visited set).
Processes each potential chain only once, avoiding the redundant work of the less efficient approach.

Cons

The logic is slightly more involved due to the management of the visited set.

Solutions

Solution

1class Solution {2public3  int maximumLength(int[] nums) {4    Map<Long, Integer> cnt = new HashMap<>();5    for (int x : nums) {6      cnt.merge((long)x, 1, Integer : : sum);7    }8    Integer t = cnt.remove(1L);9    int ans = t == null ? 0 : t - (t % 2 ^ 1);10    for (long x : cnt.keySet()) {11      t = 0;12      while (cnt.getOrDefault(x, 0) > 1) {13        x = x * x;14        t += 2;15      }16      t += cnt.getOrDefault(x, -1);17      ans = Math.max(ans, t);18    }19    return ans;20  }21}

1class Solution:2    def maximumLength(self, nums: List[int]) -> int: cnt = Counter(nums) ans = cnt[1] - (cnt[1] % 2 ^ 1) del cnt[1] for x in cnt: t = 0 while cnt[x] > 1: x = x * x t += 2 t += 1 if cnt[x] else - 1 ans = max(ans, t) return ans

1class Solution {2public:3  int maximumLength(vector<int> &nums) {4    unordered_map<long long, int> cnt;5    for (int x : nums) {6      ++cnt[x];7    }8    int ans = cnt[1] - (cnt[1] % 2 ^ 1);9    cnt.erase(1);10    for (auto [v, _] : cnt) {11      int t = 0;12      long long x = v;13      while (cnt.count(x) && cnt[x] > 1) {14        x = x * x;15        t += 2;16      }17      t += cnt.count(x) ? 1 : -1;18      ans = max(ans, t);19    }20    return ans;21  }22};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem