Given an integer array nums, find the maximum possible bitwise OR of a subset of nums and return the number of different non-empty subsets with the maximum bitwise OR.
An array a is a subset of an array b if a can be obtained from b by deleting some (possibly zero) elements of b. Two subsets are considered different if the indices of the elements chosen are different.
The bitwise OR of an array a is equal to a[0] OR a[1] OR ... OR a[a.length - 1] (0-indexed).
Example 1:
Input: nums = [3,1] Output: 2 Explanation: The maximum possible bitwise OR of a subset is 3. There are 2 subsets with a bitwise OR of 3: - [3] - [3,1]
Example 2:
Input: nums = [2,2,2] Output: 7 Explanation: All non-empty subsets of [2,2,2] have a bitwise OR of 2. There are 23 - 1 = 7 total subsets.
Example 3:
Input: nums = [3,2,1,5] Output: 6 Explanation: The maximum possible bitwise OR of a subset is 7. There are 6 subsets with a bitwise OR of 7: - [3,5] - [3,1,5] - [3,2,5] - [3,2,1,5] - [2,5] - [2,1,5]
Constraints:
1 <= nums.length <= 161 <= nums[i] <= 105class Solution {
public int countMaxOrSubsets(int[] nums) {
int n = nums.length, maxOr = 0, totalSubsets = 1 << n, ans = 0;
for (int i : nums)
maxOr |= i;
for (int bitMask = 0; bitMask < totalSubsets; bitMask++) {
int or = 0;
for (int i = 0; i < n; i++)
if (((bitMask >> i) & 1) == 1)
or |= nums[i];
if (or == maxOr)
ans++;
}
return ans;
}
}class Solution {
int[] nums;
int n, maxOr;
int[][] memo;
public int countMaxOrSubsets(int[] nums) {
this.nums = nums;
this.n = nums.length;
maxOr = 0;
for (int i : nums)
maxOr |= i;
this.memo = new int[n + 1][maxOr + 1];
for (int[] idx : memo)
Arrays.fill(idx, -1);
return solve(0, 0);
}
private int solve(int idx, int or) {
if (idx == n)
return maxOr == or ? 1 : 0;
if (memo[idx][or] != -1)
return memo[idx][or];
// System.out.println(idx + "\t" + or);
return memo[idx][or] = solve(idx + 1, or | nums[idx]) + solve(idx + 1, or);
}
}class Solution {
int[] nums;
int n, maxOr;
public int countMaxOrSubsets(int[] nums) {
this.nums = nums;
this.n = nums.length;
maxOr = 0;
for (int i : nums)
maxOr |= i;
return solve(0, 0);
}
private int solve(int idx, int or) {
if (idx == n)
return maxOr == or ? 1 : 0;
// System.out.println(idx + "\t" + or);
return solve(idx + 1, or | nums[idx]) + solve(idx + 1, or);
}
}class Solution {
public int countMaxOrSubsets(int[] nums) {
int maxOR = 0;
for (int n : nums)
maxOR |= n;
return count(nums, maxOR, 0, 0);
}
private int count(int[] nums, int maxOR, int idx, int curOR) {
if (idx == nums.length)
return curOR == maxOR ? 1 : 0;
return count(nums, maxOR, idx + 1, nums[idx] | curOR) + count(nums, maxOR, idx + 1, curOR);
}
}