Find the Maximum Number of Elements in Subset

Medium
1812.

Find the Maximum Number of Elements in Subset

Find the Maximum Number of Elements in Subset is a medium coding problem on arrays, hash table and enumeration, asked in Google interviews.

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^5
  • 1 <= nums[i] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumLength = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • 1 <= nums[i] <= 10^9

Hints for Find the Maximum Number of Elements in Subset

  1. 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.

  2. 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.

  3. Hint 3

    1 is special: 1^2 = 1, so all ones form one chain whose length must be odd. Squares overflow 32 bits — once the value passes 10^9 it 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

  1. Count every value in a hash map.
  2. For the value 1, the best is cnt[1] if odd, else cnt[1] - 1.
  3. For each distinct x > 1: set len = 0, cur = x. While cnt[cur] >= 2, add 2 and set cur = cur^2 (stop looking it up once it exceeds 10^9).
  4. Then if cnt[cur] >= 1 add 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 best

Java

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