Find the Maximum Number of Elements in Subset

MEDIUM

Description

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 2² == 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

Checkout 2 different approaches to solve Find the Maximum Number of Elements in Subset. Click on different approaches to view the approach and algorithm in detail.

Iterating Through All Potential Bases

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

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 Analysis

Time Complexity: 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 Complexity: O(U), for storing the frequency map.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Find the Maximum Number of Elements in Subset. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Find the Maximum Number of Elements in Subset

Patterns:

Enumeration

Data Structures:

ArrayHash Table