Largest Selection That Forms a Symmetric Power Pattern
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Largest Selection That Forms a Symmetric Power Pattern
You are given an array `nums` of positive integers. Select some of its elements, using each array occurrence at most once. The selected elements may be rearranged.
A selection is valid if, for some positive integer `x` and integer height `h >= 0`, it can be arranged as:
```text
[y0, y1, ..., yh, y(h-1), ..., y1, y0]
where y0 = x and y(r+1) = yr * yr
```
There is one central element and matching elements on either side. Height zero means the single-element list `[x]`. For example, height two gives `[x, x^2, x^4, x^2, x]`; the exponents increase by doubling toward the center.
Return the maximum number of elements in a valid selection.
### Examples
**Example 1**
```text
Input: nums = [3,3,9,9,81,4]
Output: 5
```
Select two copies of `3`, two copies of `9`, and one `81`, then arrange them as `[3,9,81,9,3]`. This uses five elements. A valid list has odd length, so six available elements cannot give a longer valid list.
**Example 2**
```text
Input: nums = [1,1,1,1,1,1,2,2,4]
Output: 5
```
Five of the six copies of `1` form a valid list. The six ones cannot all be used because the length must be odd. The other values can form `[2,4,2]`, of length three; they cannot be mixed into a list based at `1`. Thus the maximum is five.
### Constraints
- `2 <= nums.length <= 10^5`.
- `1 <= nums[i] <= 10^9`.
### Clarifying Questions
- Does “selection” require distinct values? No; repeated values may be chosen when enough occurrences exist in `nums`.
- Must the chosen elements remain in their original order? No; rearrangement is allowed.
- Is a one-element selection valid? Yes; it is the height-zero case.
- May the base value be `1`? Yes; the input permits it and the same pattern definition applies.
- Must a maximizing selection be returned? No; return only its length.
### C++ Interface
```cpp
class Solution {
public:
int maximumLength(vector<int>& nums) {
}
};
```
### Reasoning Checkpoints
- Match the exact power pattern while respecting available occurrences and permitting rearrangement.
- Cover every allowed base value and justify that the returned length is maximal.
- Keep arithmetic and resource use valid under the stated bounds.
```hint Count copies at each possible level
For a base greater than one, each value below the center needs two copies, while the center needs one. Consider each present value as a base and follow successive squares. Handle base one separately, since squaring it does not produce a larger value.
```
Overview: Find the largest selection of array occurrences that can be rearranged into a symmetric power pattern, with exact multiplicity and positive-value rules.