Skip to main content
Talentd

Find the Maximum Number of Elements in Subset - Solution & Explanation

MediumArrayHash TableEnumeration18 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given an array of integers and must select the largest subset that can be arranged into a symmetric sequence where values follow repeated squaring. A valid structure looks like x, x^2, x^4, ... , x^4, x^2, x. The goal is to maximize the number of elements while respecting the required power relationship between neighbors.

Approach 1: Count Frequency and Form Palindrome (Time: O(n + u log M), Space: O(u))

This approach uses a frequency map to count how often each number appears. For every possible starting value x, repeatedly check whether x, x^2, x^4, and further powers exist using fast hash lookups. Each level of the chain needs at least two occurrences to maintain symmetry on both sides of the sequence. The only exception is the middle element, which can appear once. Handling the value 1 requires special treatment because squaring never changes it, so the answer becomes the largest odd frequency of 1. This method relies heavily on hash table lookups and iterating through unique values in the array.

Approach 2: Using Power Properties (Time: O(n log M), Space: O(u))

This approach focuses on the mathematical property that every next element is the square of the previous one. Build a frequency map, then treat each number as a potential start of a power chain. Repeatedly square the current value and verify its presence in the map. If a value appears at least twice, it can extend the symmetric sequence on both sides. Once a value appears only once, it can act as the center and the chain stops. This method essentially performs controlled enumeration over possible bases while using constant‑time hash lookups to validate each power.

Recommended for interviews: The power‑property approach is what most interviewers expect. It demonstrates that you spotted the repeated squaring pattern and used a hash map to verify the chain efficiently. Showing the frequency-based reasoning first proves you understand the symmetry constraint, but the optimized enumeration of power chains highlights stronger algorithmic insight.

Approach 1: Count Frequency and Form Palindrome

This approach involves finding the occurrences of each number in the array and forming the maximal subset that can be arranged into the palindrome pattern described.

This solution first sorts the array to group identical elements together. It then iterates through the array, counting the number of times each unique number appears. The maximum number of elements we can get is the sum of floor(count/2) for each element (representing a symmetrical position in the pattern) plus one for a central element if needed.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting, where n is the number of elements in the array.
Space Complexity: O(1) additional space, as we're only storing counters.

Try this approach in the editor →

Approach 2: Using Power Properties

Here we exploit the mathematical properties of powers of 2 to directly compute the maximum subset possible without traversing explicitly looking for subsets.

This implementation exploits powers of 2 by iterating through each element's next possible power. Using the modulus operation, it checks if it divides without remainder. As proper subsets organized by powers assure the best distribution, we check the maximum potential subsets a certain power can create before upgrading to the next.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log(n)); because we iterate through powers exponentially but within linear element passes.
Space Complexity: O(1) additional space since only counters are used.

Try this approach in the editor →

Approach 3: Hash Table + Enumeration

We use a hash table cnt to record the occurrence count of each element in the array nums. For each element x, we can keep squaring it until its count in the hash table cnt is less than 2. At this point, we check if the count of x in the hash table cnt is 1. If it is, it means that x can still be included in the subset. Otherwise, we need to remove an element from the subset to ensure the subset count is odd. Then we update the answer and continue to enumerate the next element.

Note that we need to handle the case of x = 1 specially.

The time complexity is O(n times log log M), and the space complexity is O(n). Here, n and M are the length of the array nums and the maximum value in the array nums, respectively.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Count Frequency and Form Palindrome

Time Complexity: O(n log n) due to sorting, where n is the number of elements in the array.
Space Complexity: O(1) additional space, as we're only storing counters.

Using Power Properties

Time Complexity: O(n log(n)); because we iterate through powers exponentially but within linear element passes.
Space Complexity: O(1) additional space since only counters are used.

Hash Table + Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Count Frequency and Form PalindromeO(n + u log M)O(u)Good for reasoning about symmetric structure and validating frequency constraints
Using Power PropertiesO(n log M)O(u)Best general solution; leverages repeated squaring pattern with hash lookups

Video Solution

Find the Maximum Number of Elements in Subset | Detailed Explanation | Dry Run | LeetCode 3020 | MIK • codestorywithMIK • 5,387 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find the Maximum Number of Elements in Subset easy or hard?
The problem is classified as Medium difficulty on LeetCode. The challenge comes from recognizing the repeated squaring pattern and correctly handling frequency constraints, especially the special case where the value 1 can appear multiple times.
Find the Maximum Number of Elements in Subset Python/Java solution
Implementations in Python or Java follow the same idea: build a frequency map, iterate through possible starting numbers, and repeatedly square the value while verifying counts. The algorithm maintains the maximum length of a valid symmetric power chain.
How to solve Find the Maximum Number of Elements in Subset in O(n)?
You first count frequencies using a hash map in O(n). Then iterate through unique values and attempt to extend a chain by repeatedly squaring the number while checking the map. Each step is a constant‑time lookup, so the overall complexity stays close to linear for typical constraints.
What is the best approach for Find the Maximum Number of Elements in Subset?
The most effective approach uses the repeated squaring property of numbers. Build a frequency hash map, then treat each value as a starting point and repeatedly check whether its squared value exists. Each level requires two occurrences to maintain symmetry, except the center element. This solution runs in about O(n log M) time with O(n) space.
Is Find the Maximum Number of Elements in Subset asked at Google/Amazon/Meta?
Problems combining hash maps with mathematical patterns like power chains frequently appear in interviews at companies such as Amazon, Google, and Meta. They test your ability to recognize numeric patterns and efficiently validate them using hash-based lookups.
What data structure is used in Find the Maximum Number of Elements in Subset?
A hash table (or hash map) is the core data structure. It stores the frequency of every number in the array, enabling constant-time checks when verifying whether squared values exist in the sequence.
What is the time complexity of Find the Maximum Number of Elements in Subset?
The typical optimized solution runs in O(n log M) time, where n is the number of elements and M is the maximum value in the array. Each candidate value forms a chain through repeated squaring while hash map lookups remain O(1). Space complexity is O(n) for storing frequencies.

Ready to solve this problem?

Practice Find the Maximum Number of Elements in Subset with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Consecutive Sequence