Find the Maximum Number of Elements in Subset — Solution
Find the Maximum Number of Elements in Subset solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Find the Maximum Number of Elements in Subset is a medium coding problem on arrays, hash table and enumeration, asked in Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Enumeration
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array of positive integers nums. Select a subset of its elements (each index used at most once) that can be arranged as
[x, x^2, x^4, ..., x^(k/2), x^k, x^(k/2), ..., x^4, x^2, x]
where k is any non-negative power of 2 — the values climb by repeated squaring to a peak and then mirror back down. For example [2, 4, 16, 4, 2] and [3, 9, 3] follow the pattern, and so does a single element [x]; [2, 4, 8, 4, 2] does not.
Return the maximum number of elements in such a subset.
Example 1
Input: nums = [5,4,1,2,2]
Output: 3
Explanation: Choose `{4, 2, 2}` and arrange it as `[2, 4, 2]`.
Example 2
Input: nums = [1,3,2,4]
Output: 1
Explanation: No value has a second copy to climb from, so a single element is the best.
Example 3
Input: nums = [1,1,1,1]
Output: 3
Explanation: Powers of 1 are all 1, so the pattern needs an odd number of 1s: three of the four.
Constraints
2 <= nums.length <= 10^51 <= nums[i] <= 10^9
Hints for Find the Maximum Number of Elements in Subset
Hint 1
Count the occurrences of every value. For a starting value
x > 1, every level below the peak is used twice and the peak once.Hint 2
Climb from
x: while the current value occurs at least twice, take two copies and square it. When you stop, the current value is the peak if it occurs once — otherwise drop back one level so the previous value becomes the peak.Hint 3
1is special:1^2 = 1, so all ones form one chain whose length must be odd. Squares overflow 32 bits — once the value passes10^9it cannot occur.
How to solve Find the Maximum Number of Elements in Subset
Fix the smallest element x of the pattern. The pattern uses two copies of x, x^2, x^4, … up to the level below the peak and one copy of the peak, so a greedy climb on a frequency map gives the best length for that x.
Approach
- Count every value in a hash map.
- For the value 1, the best is
cnt[1]if odd, elsecnt[1] - 1. - For each distinct
x > 1: setlen = 0,cur = x. Whilecnt[cur] >= 2, add 2 and setcur = cur^2(stop looking it up once it exceeds10^9). - Then if
cnt[cur] >= 1add 1 (it is the peak), otherwise subtract 1 (the last pair's value becomes the single peak). Track the maximum.
Why it works
For a fixed x > 1 the levels x^(2^i) are distinct and increasing, so the pattern of height t is available iff each of the first t levels occurs twice and level t once. The greedy climb finds the largest t with all lower levels doubled; if level t has no copy, level t - 1 (which has two) can serve as the peak, giving 2t - 1. Since the climb starts at a value present in nums, every x yields at least 1.
Complexity
- Time —
O(n log log V) - Space —
O(n)
Pitfalls
- Squaring in 32-bit arithmetic overflows — use 64-bit and stop once past
10^9. - Treating 1 like any other base loops forever, since
1^2 = 1. - An even number of 1s cannot all be used — the pattern has odd length.
Reference solution
Python
from typing import List
from collections import Counter
def maximumLength(nums: List[int]) -> int:
cnt = Counter(nums)
ones = cnt.get(1, 0)
best = ones if ones % 2 == 1 else max(ones - 1, 0)
for x in cnt:
if x == 1:
continue
length, cur = 0, x
while cnt.get(cur, 0) >= 2:
length += 2
cur *= cur
length += 1 if cnt.get(cur, 0) >= 1 else -1
best = max(best, length)
return bestJava
public static int maximumLength(int[] nums) {
HashMap<Long, Integer> cnt = new HashMap<>();
for (int v : nums) cnt.merge((long) v, 1, Integer::sum);
int ones = cnt.getOrDefault(1L, 0);
int best = ones % 2 == 1 ? ones : Math.max(ones - 1, 0);
for (long x : cnt.keySet()) {
if (x == 1) continue;
int len = 0;
long cur = x;
while (cnt.getOrDefault(cur, 0) >= 2) {
len += 2;
cur = cur * cur; // at most 10^18 — fits a long, and is then simply absent
}
len += cnt.getOrDefault(cur, 0) >= 1 ? 1 : -1;
best = Math.max(best, len);
}
return best;
}C++
int maximumLength(vector<int>& nums) {
unordered_map<long long, int> cnt;
for (int v : nums) cnt[v]++;
int ones = cnt.count(1) ? cnt[1] : 0;
int best = ones % 2 == 1 ? ones : max(ones - 1, 0);
for (auto& kv : cnt) {
long long x = kv.first;
if (x == 1) continue;
int len = 0;
long long cur = x;
while (true) {
auto it = cnt.find(cur);
if (it == cnt.end() || it->second < 2) break;
len += 2;
cur = cur * cur;
}
len += cnt.count(cur) ? 1 : -1;
best = max(best, len);
}
return best;
}JavaScript
var maximumLength = function(nums) {
var cnt = new Map();
for (var i = 0; i < nums.length; i++) cnt.set(nums[i], (cnt.get(nums[i]) || 0) + 1);
var ones = cnt.get(1) || 0;
var best = ones % 2 === 1 ? ones : Math.max(ones - 1, 0);
cnt.forEach(function(c, x) {
if (x === 1) return;
var len = 0, cur = x;
while (cur <= 1000000000 && (cnt.get(cur) || 0) >= 2) {
len += 2;
cur = cur * cur;
}
len += cur <= 1000000000 && (cnt.get(cur) || 0) >= 1 ? 1 : -1;
if (len > best) best = len;
});
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets