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.
1import java.util.*;
2
3public class MaxOrSubsets {
4 private int maxOr = 0;
5 private int count = 0;
6
7 public int countMaxOrSubsets(int[] nums) {
8 maxOr = 0;
9 count = 0;
10 findAllSubsets(nums, 0, 0);
11 return count;
12 }
13
14 private void findAllSubsets(int[] nums, int index, int currentOr) {
15 if (index == nums.length) {
16 if (currentOr > maxOr) {
17 maxOr = currentOr;
18 count = 1;
19 } else if (currentOr == maxOr) {
20 count++;
21 }
22 return;
23 }
24 findAllSubsets(nums, index + 1, currentOr | nums[index]);
25 findAllSubsets(nums, index + 1, currentOr);
26 }
27
28 public static void main(String[] args) {
29 MaxOrSubsets solution = new MaxOrSubsets();
30 int[] nums = {3, 2, 1, 5};
31 System.out.println("Output: " + solution.countMaxOrSubsets(nums));
32 }
33}In this Java solution, findAllSubsets() is a recursive private helper method that performs the same task as previously described: keeping track of on-the-fly OR calculations for each subset and updating the maximum OR and count accordingly.
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.
public class Solution {
public int CountMaxOrSubsets(int[] nums) {
int maxOr = 0;
int count = 0;
int n = nums.Length;
int totalSubsets = 1 << n;
for (int mask = 1; mask < totalSubsets; ++mask) {
int orValue = 0;
for (int i = 0; i < n; ++i) {
if ((mask & (1 << i)) != 0) {
orValue |= nums[i];
}
}
if (orValue > maxOr) {
maxOr = orValue;
count = 1;
} else if (orValue == maxOr) {
count++;
}
}
return count;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {3, 2, 1, 5};
Console.WriteLine("Output: " + sol.CountMaxOrSubsets(nums));
}
}Within this C# solution, mask operations allow subset identification along numeric combinations. As each subset OR is computed, it's measured against the maximum OR, and their count tallied efficiently.