We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Maximum Number of Elements in Subset

Number: 3299

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an array of positive integers, we need to choose a subset of elements such that after reordering, they form a symmetric “power‐chain” array that follows the pattern: [x, x², x⁴, …, x^(k/2), x^(k), x^(k/2), …, x⁴, x², x] where k is any non-negative power of 2. In other words, aside from the single element case, the pattern requires that the first element appears twice (as the first and last element), the second element appears twice, and so on—with the “middle” element only appearing once. For example, [2,4,16,4,2] and [3,9,3] are valid while [2,4,8,4,2] is not. The goal is to return the maximum number of elements a subset can have while still being able to order them to fit this pattern.

Key Insights

  • The valid pattern is symmetric with paired elements on both sides except possibly the center.
  • If we pick a base x, to form a valid pattern longer than just [x] (length 1), we need at least two occurrences of x.
  • The chain is generated by repeatedly squaring the previous element. For a chain starting with x, the next required element is x²; then (x²)² = x⁴; and so on.
  • For each extension step (beyond the very last element), the element used in the symmetric pair must appear at least twice, whereas the center element only needs to appear once.
  • We can compute the maximum chain length from each candidate base x (using frequency counts) and then return the maximum over all bases.

Space and Time Complexity

Time Complexity: O(n * log(max(nums))) – We iterate over each unique element from the array (O(n)) and for each, we potentially extend the chain in a logarithmic number of steps with respect to the magnitude of values. Space Complexity: O(n) – For storing the frequency count of the numbers.

Solution

We use a frequency map (hash table) to count occurrences of each number. For each unique number x in the array:

  1. A chain of length 1 (i.e. just [x]) is always valid if x appears at least once.
  2. To extend the chain into a valid pattern (e.g., [x, x², x]), x must appear at least twice and x² must exist in the map.
  3. Once we have a chain of length 3, each further extension requires that the current “middle” number (say, y) appears at least twice (since it will appear in symmetric positions) and that y² exists, so that the pattern can be extended by two.
  4. We update the maximum chain length over all possible starting x values. The algorithm then returns this maximum chain length as the answer.

Code Solutions

from collections import Counter

def maximumSubsetElements(nums):
    # Count frequency of each number in nums.
    freq = Counter(nums)
    # Initialize maximum chain length to 1 (any single number is valid)
    max_chain = 1

    # Iterate over every unique number as a potential starting base.
    for x in freq:
        # A single element [x] is always valid.
        chain_length = 1
        
        # To form a longer pattern, x must appear at least twice.
        if freq[x] < 2:
            max_chain = max(max_chain, chain_length)
            continue
        
        # Attempt to extend the chain with candidate = x^2.
        candidate = x * x
        if candidate not in freq:
            max_chain = max(max_chain, chain_length)
            continue
        
        # We can form [x, candidate, x] so start with chain length 3.
        chain_length = 3
        current = candidate
        
        # Try to further extend the chain.
        while True:
            next_candidate = current * current
            # To use current as a symmetric pair member, it must appear at least twice.
            if freq[current] < 2:
                break
            # The extension is possible only if the next candidate exists.
            if next_candidate not in freq:
                break
            chain_length += 2  # Increase length by 2 for the new pair.
            current = next_candidate
        max_chain = max(max_chain, chain_length)
    
    return max_chain

# Example usage:
print(maximumSubsetElements([5,4,1,2,2]))  # Expected output: 3
print(maximumSubsetElements([1,3,2,4]))    # Expected output: 1
← Back to All Questions