Find the Maximum Number of Elements in Subset

Find the Maximum Number of Elements in Subset - Problem

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] where k can be any non-negative power of 2.

Note: The pattern forms a symmetric sequence where powers increase to the middle then decrease.

Examples of valid patterns:

[2, 4, 16, 4, 2] follows the pattern (x=2, k=4)
[3, 9, 3] follows the pattern (x=3, k=2)
[5] follows the pattern (x=5, k=0)

Invalid pattern: [2, 4, 8, 4, 2] does not follow the pattern because 8 ≠ 2⁴

Return the maximum number of elements in a subset that satisfies these conditions.

Input & Output

Example 1 — Valid Symmetric Pattern

$ Input: nums = [2,4,16,4,2]

› Output: 5

💡 Note: All elements can form pattern [2,4,16,4,2] where x=2, powers are [2¹,2²,2⁴,2²,2¹] - perfectly symmetric

Example 2 — Multiple Options

$ Input: nums = [2,4,8,16]

› Output: 3

💡 Note: Can form [2,4,2] using x=2 (length 3) or [4,16,4] using x=4 (length 3). Cannot use 8 as 8≠2⁴

Example 3 — Single Element

$ Input: nums = [5]

› Output: 1

💡 Note: Pattern [5] with x=5, k=0 is valid - single element always forms valid pattern

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array of positive integers [2,4,16,4,2]

Pattern Recognition

Find symmetric power sequences: [x, x², x⁴, x², x]

Maximum Length

Return length of longest valid symmetric subset

Key Takeaway

🎯 Key Insight: Valid subsets must form symmetric patterns where elements follow power sequences of a base number

Asked in

G Google 25 f Meta 18 a Amazon 15

The key insight is that valid subsets form symmetric patterns based on power sequences of base numbers. Count frequencies of each number, then for each potential base, try to build the longest power chain (base, base², base⁴, ...) and check if we have enough elements to form a symmetric pattern. Best approach uses frequency counting with chain building. Time: O(n × log(log(max_val))), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Subsets	O(2ⁿ × n)	O(n)	Generate all possible subsets and check which ones form valid symmetric patterns
Frequency Count with Chain Building	O(n × log(log(max_val)))	O(n)	Count frequencies and build the longest valid chain for each possible base

Brute Force - Try All Subsets — Algorithm Steps

Generate all possible subsets of the array
For each subset, try to arrange elements in symmetric pattern
Check if the arrangement follows x, x², x⁴, ... power sequence
Keep track of maximum valid subset length

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subsets

Create all 2ⁿ possible subsets

Validate Pattern

Check if subset can form symmetric power sequence

Find Maximum

Return length of longest valid subset

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool isValidPattern(int* subset, int size) {
    if (size == 0) return true;
    
    // Simple validation - check if can form symmetric pattern
    // This is a simplified version for demonstration
    int count[100001] = {0};
    for (int i = 0; i < size; i++) {
        count[subset[i]]++;
    }
    
    for (int i = 0; i < size; i++) {
        int base = subset[i];
        if (count[base] == 0) continue;
        
        int chain[20];
        int chainSize = 1;
        chain[0] = base;
        long long current = base;
        
        int tempCount[100001];
        memcpy(tempCount, count, sizeof(count));
        tempCount[base]--;
        
        while (chainSize < 20) {
            long long nextVal = current * current;
            if (nextVal > 100000 || tempCount[nextVal] == 0) break;
            chain[chainSize++] = (int)nextVal;
            tempCount[nextVal]--;
            current = nextVal;
        }
        
        // Check if this forms valid pattern
        int patternCount[100001] = {0};
        for (int j = 0; j < chainSize; j++) {
            patternCount[chain[j]]++;
        }
        for (int j = chainSize - 2; j >= 0; j--) {
            patternCount[chain[j]]++;
        }
        
        bool match = true;
        for (int j = 1; j <= 100000; j++) {
            if (patternCount[j] != count[j]) {
                match = false;
                break;
            }
        }
        if (match) return true;
    }
    
    return false;
}

int backtrack(int* nums, int n, int index, int* currentSubset, int subsetSize) {
    if (index == n) {
        return isValidPattern(currentSubset, subsetSize) ? subsetSize : 0;
    }
    
    currentSubset[subsetSize] = nums[index];
    int include = backtrack(nums, n, index + 1, currentSubset, subsetSize + 1);
    
    int exclude = backtrack(nums, n, index + 1, currentSubset, subsetSize);
    
    return include > exclude ? include : exclude;
}

int solution(int* nums, int n) {
    int* currentSubset = (int*)malloc(n * sizeof(int));
    int result = backtrack(nums, n, 0, currentSubset, 0);
    free(currentSubset);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int n = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ × n)

Generate 2ⁿ subsets, each taking O(n) time to validate the pattern

✓ Linear Growth

Space Complexity

O(n)

Space for storing current subset and recursion stack

⚡ Linearithmic Space

26.8K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Subsets — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler