Find the Maximum Number of Elements in Subset
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^2, x^4, ..., x^k/2, x^k, x^k/2, ..., x^4, x^2, x], wherekcan be any non-negative power of2.
Return the maximum number of elements in a subset that satisfies these conditions.
Example 1
Input
nums = [5,4,1,2,2]Output
3We can select the subset {4,2,2}, which can be placed as [2,4,2], following the pattern because 2^2 == 4.
Example 2
Input
nums = [1,3,2,4]Output
1We can select the subset {1}, which can be placed as [1], and other single-element subsets would also give the same answer.
Constraints
- 2 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^9