# Find the Maximum Number of Elements in Subset
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-maximum-number-of-elements-in-subset)
Canonical: https://scaleengineer.com/dsa/problems/find-the-maximum-number-of-elements-in-subset
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array, Hash Table
---
## 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, 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
## 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.
**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.
**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.
### Explanation
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:**

```java
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;
    }
}
```
### 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:**

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

## Optimized Approach with Frequency Map and Memoization
This approach improves upon the previous one by avoiding redundant computations. We still use a frequency map, but we ensure that each potential geometric progression (`x, x^2, x^4, ...`) is processed only once. We can achieve this by keeping track of numbers that have already been considered as part of a longer chain.
**Time:** O(N + U * log M), where `N` is the length of `nums`, `U` is the number of unique elements, and `M` is the maximum value. `O(N)` is for building the frequency map. The main loop iterates up to `U` times. The inner `while` loop for a number `x` involves repeated squaring, so it runs at most `log(M)` times. Since we use a `visited` set, each chain is processed only once. · **Space:** O(U), for the frequency map and the `visited` set.
**Pros:** Highly efficient due to memoization (using the `visited` set).; Processes each potential chain only once, avoiding the redundant work of the less efficient approach.
**Cons:** The logic is slightly more involved due to the management of the `visited` set.
### Explanation
The key insight is that if we have a chain starting with `x`, any chain starting with `x^2`, `x^4`, etc., will be shorter or equal in length. Therefore, we only need to start checking from the smallest possible base of a chain. We can use a `visited` set to mark numbers that have been processed.

*   **Algorithm:**
    1.  Count the frequencies of all numbers and store them in a map.
    2.  Initialize `maxLen`. Handle the special case of the number `1` as before. The minimum answer is `1` if the array is not empty.
    3.  Create a `visited` set to store numbers that have already been part of a chain calculation.
    4.  Iterate through each unique number `num` from the frequency map.
    5.  If `num` is `1` or has been `visited`, skip it.
    6.  A number `num` can only serve as a non-peak element in the pattern if its count is at least 2. If `count[num] < 2`, it cannot be the base of a symmetric pattern, so we skip it. (The case `[num]` is already covered by `maxLen` initialization).
    7.  If `count[num] >= 2`, we start building a chain: `num, num^2, num^4, ...`.
    8.  Initialize the current subset length to `1` (for the pattern `[num]`).
    9.  In a loop, calculate the next term `next_val = current_num^2`. Mark `next_val` as visited.
    10. If `next_val` exists in our frequency map:
        *   If `count[next_val] >= 2`, we can extend the symmetric part of our pattern. Add `2` to the current length.
        *   If `count[next_val] == 1`, this number must be the peak. We add `2` to the length and terminate the chain building for this base.
    11. If `next_val` does not exist, the chain ends.
    12. Update the overall `maxLen` with the length found for the current chain.

*   **Code Snippet:**

```java
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class Solution {
    public int maximumLength(int[] nums) {
        Map<Long, Integer> counts = new HashMap<>();
        boolean hasElements = nums.length > 0;
        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;
        }
        if (hasElements) {
            maxLen = Math.max(maxLen, 1);
        }

        Set<Long> visited = new HashSet<>();

        for (long num : counts.keySet()) {
            if (num == 1 || visited.contains(num)) {
                continue;
            }

            if (counts.get(num) < 2) {
                continue;
            }

            int currentLen = 1;
            long currentNum = num;
            visited.add(currentNum);

            while (true) {
                long nextNum = currentNum * currentNum;
                if (nextNum > 1_000_000_000L) {
                    break;
                }
                visited.add(nextNum);
                if (!counts.containsKey(nextNum)) {
                    break;
                }

                if (counts.get(nextNum) >= 2) {
                    currentLen += 2;
                } else { // count == 1
                    currentLen += 2;
                    break;
                }
                currentNum = nextNum;
            }
            maxLen = Math.max(maxLen, currentLen);
        }

        return maxLen;
    }
}
```
### Algorithm
*   **Algorithm:**
    1.  Count the frequencies of all numbers and store them in a map.
    2.  Initialize `maxLen`. Handle the special case of the number `1` as before. The minimum answer is `1` if the array is not empty.
    3.  Create a `visited` set to store numbers that have already been part of a chain calculation.
    4.  Iterate through each unique number `num` from the frequency map.
    5.  If `num` is `1` or has been `visited`, skip it.
    6.  A number `num` can only serve as a non-peak element in the pattern if its count is at least 2. If `count[num] < 2`, it cannot be the base of a symmetric pattern, so we skip it. (The case `[num]` is already covered by `maxLen` initialization).
    7.  If `count[num] >= 2`, we start building a chain: `num, num^2, num^4, ...`.
    8.  Initialize the current subset length to `1` (for the pattern `[num]`).
    9.  In a loop, calculate the next term `next_val = current_num^2`. Mark `next_val` as visited.
    10. If `next_val` exists in our frequency map:
        *   If `count[next_val] >= 2`, we can extend the symmetric part of our pattern. Add `2` to the current length.
        *   If `count[next_val] == 1`, this number must be the peak. We add `2` to the length and terminate the chain building for this base.
    11. If `next_val` does not exist, the chain ends.
    12. Update the overall `maxLen` with the length found for the current chain.

*   **Code Snippet:**

```java
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class Solution {
    public int maximumLength(int[] nums) {
        Map<Long, Integer> counts = new HashMap<>();
        boolean hasElements = nums.length > 0;
        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;
        }
        if (hasElements) {
            maxLen = Math.max(maxLen, 1);
        }

        Set<Long> visited = new HashSet<>();

        for (long num : counts.keySet()) {
            if (num == 1 || visited.contains(num)) {
                continue;
            }

            if (counts.get(num) < 2) {
                continue;
            }

            int currentLen = 1;
            long currentNum = num;
            visited.add(currentNum);

            while (true) {
                long nextNum = currentNum * currentNum;
                if (nextNum > 1_000_000_000L) {
                    break;
                }
                visited.add(nextNum);
                if (!counts.containsKey(nextNum)) {
                    break;
                }

                if (counts.get(nextNum) >= 2) {
                    currentLen += 2;
                } else { // count == 1
                    currentLen += 2;
                    break;
                }
                currentNum = nextNum;
            }
            maxLen = Math.max(maxLen, currentLen);
        }

        return maxLen;
    }
}
```

# Solutions
### Java

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

```

### Python

```python
class Solution:
    def maximumLength(self, nums: List[int]) -> int: cnt = Counter(nums) ans = cnt[1] - (cnt[1] % 2 ^ 1) del cnt[1] for x in cnt: t = 0 while cnt[x] > 1: x = x * x t += 2 t += 1 if cnt[x] else - 1 ans = max(ans, t) return ans

```

### CPP

```cpp
class Solution {
public:
  int maximumLength(vector<int> &nums) {
    unordered_map<long long, int> cnt;
    for (int x : nums) {
      ++cnt[x];
    }
    int ans = cnt[1] - (cnt[1] % 2 ^ 1);
    cnt.erase(1);
    for (auto [v, _] : cnt) {
      int t = 0;
      long long x = v;
      while (cnt.count(x) && cnt[x] > 1) {
        x = x * x;
        t += 2;
      }
      t += cnt.count(x) ? 1 : -1;
      ans = max(ans, t);
    }
    return ans;
  }
};

```