Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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 summary: 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, 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Hash Map
[5,4,1,2,2]
[1,3,2,4]
longest-consecutive-sequence)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3020: Find the Maximum Number of Elements in Subset
class Solution {
public int maximumLength(int[] nums) {
Map<Long, Integer> cnt = new HashMap<>();
for (int x : nums) {
cnt.merge((long) x, 1, Integer::sum);
}
Integer t = cnt.remove(1L);
int ans = t == null ? 0 : t - (t % 2 ^ 1);
for (long x : cnt.keySet()) {
t = 0;
while (cnt.getOrDefault(x, 0) > 1) {
x = x * x;
t += 2;
}
t += cnt.getOrDefault(x, -1);
ans = Math.max(ans, t);
}
return ans;
}
}
// Accepted solution for LeetCode #3020: Find the Maximum Number of Elements in Subset
func maximumLength(nums []int) (ans int) {
cnt := map[int]int{}
for _, x := range nums {
cnt[x]++
}
ans = cnt[1] - (cnt[1]%2 ^ 1)
delete(cnt, 1)
for x := range cnt {
t := 0
for cnt[x] > 1 {
x = x * x
t += 2
}
if cnt[x] > 0 {
t += 1
} else {
t -= 1
}
ans = max(ans, t)
}
return
}
# Accepted solution for LeetCode #3020: Find the Maximum Number of Elements in Subset
class Solution:
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
// Accepted solution for LeetCode #3020: Find the Maximum Number of Elements in Subset
use std::collections::HashMap;
impl Solution {
pub fn maximum_length(nums: Vec<i32>) -> i32 {
let mut cnt: HashMap<i64, i32> = HashMap::new();
for &x in &nums {
*cnt.entry(x as i64).or_insert(0) += 1;
}
let mut ans = 0;
if let Some(t) = cnt.remove(&1) {
ans = t - ((t % 2) ^ 1);
}
for &key in cnt.keys() {
let mut x = key;
let mut t = 0;
while *cnt.get(&x).unwrap_or(&0) > 1 {
x = x * x;
t += 2;
}
t += cnt.get(&x).unwrap_or(&-1);
ans = ans.max(t);
}
ans
}
}
// Accepted solution for LeetCode #3020: Find the Maximum Number of Elements in Subset
function maximumLength(nums: number[]): number {
const cnt: Map<number, number> = new Map();
for (const x of nums) {
cnt.set(x, (cnt.get(x) ?? 0) + 1);
}
let ans = cnt.has(1) ? cnt.get(1)! - ((cnt.get(1)! % 2) ^ 1) : 0;
cnt.delete(1);
for (let [x, _] of cnt) {
let t = 0;
while (cnt.has(x) && cnt.get(x)! > 1) {
x = x * x;
t += 2;
}
t += cnt.has(x) ? 1 : -1;
ans = Math.max(ans, t);
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.