Scale Engineer

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
ArrayHash 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, 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 <= 105
  • 1 <= nums[i] <= 109

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:

import java.util.HashMap;import java.util.Map; class Solution {    public int maximumLength(int[] nums) {        Map<Long, Integer> counts = new HashMap<>();        for (int num : nums) {            counts.put((long)num, counts.getOrDefault((long)num, 0) + 1);        }         int maxLen = 0;        int countOfOnes = counts.getOrDefault(1L, 0);        if (countOfOnes > 0) {            maxLen = (countOfOnes % 2 == 1) ? countOfOnes : countOfOnes - 1;        }        // Any single element can form a subset of size 1        if (nums.length > 0) {             maxLen = Math.max(maxLen, 1);        }         for (long x : counts.keySet()) {            if (x == 1) continue;             // Check for chains starting with x            long currentNum = x;            int p = 0;            while (true) {                // Check if pattern with peak x^(2^p) is possible                boolean possible = true;                long peak = currentNum;                if (counts.getOrDefault(peak, 0) < 1) {                    possible = false;                }                 long tempNum = x;                for (int i = 0; i < p; i++) {                    if (counts.getOrDefault(tempNum, 0) < 2) {                        possible = false;                        break;                    }                    tempNum = tempNum * tempNum;                }                 if (possible) {                    maxLen = Math.max(maxLen, 2 * p + 1);                    long nextNum = currentNum * currentNum;                    if (nextNum > 1_000_000_000L) break;                    currentNum = nextNum;                    p++;                } else {                    break;                }            }        }         return maxLen;    }}

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:

import java.util.HashMap;import java.util.Map; class Solution {    public int maximumLength(int[] nums) {        Map<Long, Integer> counts = new HashMap<>();        for (int num : nums) {            counts.put((long)num, counts.getOrDefault((long)num, 0) + 1);        }         int maxLen = 0;        int countOfOnes = counts.getOrDefault(1L, 0);        if (countOfOnes > 0) {            maxLen = (countOfOnes % 2 == 1) ? countOfOnes : countOfOnes - 1;        }        // Any single element can form a subset of size 1        if (nums.length > 0) {             maxLen = Math.max(maxLen, 1);        }         for (long x : counts.keySet()) {            if (x == 1) continue;             // Check for chains starting with x            long currentNum = x;            int p = 0;            while (true) {                // Check if pattern with peak x^(2^p) is possible                boolean possible = true;                long peak = currentNum;                if (counts.getOrDefault(peak, 0) < 1) {                    possible = false;                }                 long tempNum = x;                for (int i = 0; i < p; i++) {                    if (counts.getOrDefault(tempNum, 0) < 2) {                        possible = false;                        break;                    }                    tempNum = tempNum * tempNum;                }                 if (possible) {                    maxLen = Math.max(maxLen, 2 * p + 1);                    long nextNum = currentNum * currentNum;                    if (nextNum > 1_000_000_000L) break;                    currentNum = nextNum;                    p++;                } else {                    break;                }            }        }         return maxLen;    }}

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.

Solutions

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;  }}

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 →

Next problem