3020. Find the Maximum Number of Elements in Subset LeetCode Solution
In this guide, you will get 3020. Find the Maximum Number of Elements in Subset LeetCode Solution with the best time and space complexity. The solution to Find the Maximum Number of Elements in Subset problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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, 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.
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
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
3020. Find the Maximum Number of Elements in Subset LeetCode Solution in C++
class Solution {
public:
int maximumLength(vector<int>& nums) {
const int maxNum = ranges::max(nums);
unordered_map<int, int> count;
for (const int num : nums)
++count[num];
int ans = count.contains(1) ? count[1] - (count[1] % 2 == 0) : 1;
for (const int num : nums) {
if (num == 1)
continue;
int length = 0;
long x = num;
while (x <= maxNum && count.contains(x) && count[x] >= 2) {
length += 2;
x *= x;
}
// x is now x^k, and the pattern is [x, ..., x^(k/2), x^(k/2), ..., x].
// The goal is to determine if we can insert x^k in the middle of the
// pattern to increase the length by 1. If not, we make x^(k/2) the middle
// and decrease the length by 1.
ans = max(ans, length + (count.contains(x) ? 1 : -1));
}
return ans;
}
}; /* code provided by PROGIEZ */
3020. Find the Maximum Number of Elements in Subset LeetCode Solution in Java
class Solution {
public int maximumLength(int[] nums) {
final int maxNum = Arrays.stream(nums).max().getAsInt();
Map<Integer, Integer> count = new HashMap<>();
for (final int num : nums)
count.merge(num, 1, Integer::sum);
int ans = count.containsKey(1) ? count.get(1) - (count.get(1) % 2 == 0 ? 1 : 0) : 1;
for (final int num : nums) {
if (num == 1)
continue;
int length = 0;
long x = num;
while (x <= maxNum && count.containsKey((int) x) && count.get((int) x) >= 2) {
length += 2;
x *= x;
}
// x is now x^k, and the pattern is [x, ..., x^(k/2), x^(k/2), ..., x].
// The goal is to determine if we can insert x^k in the middle of the
// pattern to increase the length by 1. If not, we make x^(k/2) the middle
// and decrease the length by 1.
ans = Math.max(ans, length + (count.containsKey((int) x) ? 1 : -1));
}
return ans;
}
} // code provided by PROGIEZ
3020. Find the Maximum Number of Elements in Subset LeetCode Solution in Python
class Solution:
def maximumLength(self, nums: list[int]) -> int:
maxNum = max(nums)
count = collections.Counter(nums)
ans = count[1] - (count[1] % 2 == 0) if 1 in count else 1
for num in nums:
if num == 1:
continue
length = 0
x = num
while x <= maxNum and x in count and count[x] >= 2:
length += 2
x *= x
# x is now x^k, and the pattern is [x, ..., x^(k/2), x^(k/2), ..., x].
# The goal is to determine if we can insert x^k in the middle of the
# pattern to increase the length by 1. If not, we make x^(k/2) the middle
# and decrease the length by 1.
ans = max(ans, length + (1 if x in count else -1))
return ans # code by PROGIEZ
