Scale Engineer

Count Number of Maximum Bitwise-OR Subsets

Med
#1861Time: O(n * 2^n). We iterate through `2^n - 1` subsets. For each subset, we iterate through up to `n` elements to check for inclusion and calculate the bitwise OR.Space: O(1). We only use a few variables to store the maximum OR value and the count, regardless of the input size.1 company
Patterns
BacktrackingBit ManipulationEnumeration
Data structures
Array
Companies
Citadel

Prompt

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 <= 16
  • 1 <= nums[i] <= 105

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves generating every possible non-empty subset of the input array nums. For each subset, we calculate the bitwise OR of its elements. We can determine the maximum OR value and count the subsets that achieve it in a single pass. A common and straightforward way to represent and iterate through all subsets for a small number of elements is by using a bitmask.

Algorithm

  • This approach can be implemented with a single pass.
  • Initialize maxOr = 0 and count = 0.
  • Iterate through all possible non-empty subsets using a bitmask i from 1 to (1 << n) - 1, where n is the length of nums.
  • For each mask i, calculate the currentOr of the corresponding subset. A number nums[j] is in the subset if the j-th bit of i is set.
  • Compare currentOr with maxOr:
    • If currentOr > maxOr, a new maximum OR value is found. Update maxOr = currentOr and reset count to 1.
    • If currentOr == maxOr, another subset with the maximum OR value is found. Increment count.
  • After iterating through all masks, count will hold the number of subsets with the maximum bitwise OR.

Walkthrough

A bitmask is an integer used to represent a set. For an array of size n, we can use an n-bit integer where the j-th bit corresponds to the j-th element of the array. If the bit is 1, the element is in the subset; if it's 0, it's not. We can loop from 1 to 2^n - 1 to generate all non-empty subsets.

class Solution {    public int countMaxOrSubsets(int[] nums) {        int n = nums.length;        int maxOr = 0;        int count = 0;                // Iterate through all 2^n - 1 non-empty subsets using a bitmask.        // Each 'i' represents a subset.        for (int i = 1; i < (1 << n); i++) {            int currentOr = 0;            // For each subset, calculate its bitwise OR.            for (int j = 0; j < n; j++) {                // Check if the j-th element is in the current subset.                if (((i >> j) & 1) == 1) {                    currentOr |= nums[j];                }            }                        // Compare the current subset's OR with the max OR found so far.            if (currentOr > maxOr) {                maxOr = currentOr;                count = 1;            } else if (currentOr == maxOr) {                count++;            }        }        return count;    }}

Complexity

Time

O(n * 2^n). We iterate through `2^n - 1` subsets. For each subset, we iterate through up to `n` elements to check for inclusion and calculate the bitwise OR.

Space

O(1). We only use a few variables to store the maximum OR value and the count, regardless of the input size.

Trade-offs

Pros

  • Simple to understand and implement.

  • Uses constant extra space.

Cons

  • This is the least efficient approach due to its time complexity. For each of the 2^n subsets, it iterates up to n times to calculate the OR value.

Solutions

class Solution {private  int mx;private  int ans;private  int[] nums;public  int countMaxOrSubsets(int[] nums) {    mx = 0;    for (int x : nums) {      mx |= x;    }    this.nums = nums;    dfs(0, 0);    return ans;  }private  void dfs(int i, int t) {    if (i == nums.length) {      if (t == mx) {        ++ans;      }      return;    }    dfs(i + 1, t);    dfs(i + 1, t | nums[i]);  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem