3020. Find the Maximum Number of Elements in Subset
Description
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 thatk
can be be any non-negative power of2
). 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
Solutions
Solution 1: 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|