Sponsored
Sponsored
This approach involves generating all subsets using a bitmask. For each possible subset generated by the bitmask, compute the bitwise OR, and keep track of the maximum bitwise OR found. After calculating the OR for all subsets, we count how many subsets achieved the maximum OR value.
Time Complexity: O(n * 2^n), where n is the length of the array. There are 2^n possible subsets and computing the OR for each subset can take O(n) in the worst case.
Space Complexity: O(n) due to recursive call stack depth.
1#include <stdio.h>
2
3int maxOrValue = 0;
4int count = 0;
5
6void countMaxOrSubsets(int* nums, int numsSize, int pos, int currentOr) {
7 if (pos == numsSize) {
8 if (currentOr > maxOrValue) {
9 maxOrValue = currentOr;
10 count = 1;
11 } else if (currentOr == maxOrValue) {
12 count++;
13 }
14 return;
15 }
16 // Include nums[pos]
17 countMaxOrSubsets(nums, numsSize, pos + 1, currentOr | nums[pos]);
18 // Exclude nums[pos]
19 countMaxOrSubsets(nums, numsSize, pos + 1, currentOr);
20}
21
22int countMaxOrSubsetsMain(int* nums, int numsSize) {
23 maxOrValue = 0;
24 count = 0;
25 countMaxOrSubsets(nums, numsSize, 0, 0);
26 return count;
27}
28
29int main() {
30 int nums[] = {3, 2, 1, 5};
31 int result = countMaxOrSubsetsMain(nums, 4);
32 printf("Output: %d\n", result);
33 return 0;
34}This solution uses a recursive helper function countMaxOrSubsets which explores all possible subsets of the input array by deciding whether to include each element in the current subset. The function keeps track of the current subset’s bitwise OR and updates the global maximum OR and corresponding count of subsets achieving this OR as necessary.
This approach employs an iterative method utilizing bitmasks to evaluate all potential subsets. For each possible subset marked by a bitmask, the bitwise OR is computed and retained if it represents a new maximum. The process counts how many subsets reach this maximal OR value, iterating over binary number representations to dynamically include or exclude each number in the subset.
Time Complexity: O(n * 2^n) - By iterating through all 2^n subsets and calculating ORs, computation scales linearly with each set size.
Space Complexity: O(1), since only fixed local variables manage computations.
#include <vector>
class Solution {
public:
int countMaxOrSubsets(std::vector<int>& nums) {
int maxOr = 0, count = 0;
int numsSize = nums.size();
int totalSubsets = 1 << numsSize;
for (int mask = 1; mask < totalSubsets; ++mask) {
int orValue = 0;
for (int i = 0; i < numsSize; ++i) {
if (mask & (1 << i)) {
orValue |= nums[i];
}
}
if (orValue > maxOr) {
maxOr = orValue;
count = 1;
} else if (orValue == maxOr) {
count++;
}
}
return count;
}
};
int main() {
Solution sol;
std::vector<int> nums = {3, 2, 1, 5};
std::cout << "Output: " << sol.countMaxOrSubsets(nums) << std::endl;
return 0;
}The C++ implementation uses bit masking to enumerate all possible subsets for calculation of subset ORs. It then updates the global maximum OR and count of such subsets to derive the result.