Count Number of Maximum Bitwise-OR Subsets

Medium
735.

Count Number of Maximum Bitwise-OR Subsets

Count Number of Maximum Bitwise-OR Subsets is a medium coding problem on bit manipulation, backtracking and enumeration, asked in Amazon, Google and Samsung interviews.

Return the number of non-empty subsets of nums whose bitwise OR is the maximum achievable.

Two subsets are different when they use different index sets, even if the values coincide.

Example 1

Input
nums = [3,1]
Output
2
Explanation
The maximum OR is 3, reached by {3} and {3,1}.

Example 2

Input
nums = [2,2,2]
Output
7
Explanation
Every non-empty subset ORs to 2.

Example 3

Input
nums = [3,2,1,5]
Output
6

Constraints

  • 1 <= nums.length <= 16
  • 1 <= nums[i] <= 100000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var countMaxOrSubsets = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Number of Maximum Bitwise-OR Subsets — Solution

Count Number of Maximum Bitwise-OR Subsets solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Count Number of Maximum Bitwise-OR Subsets is a medium coding problem on bit manipulation, backtracking and enumeration, asked in Amazon, Google and Samsung interviews.

Problem statement

Return the number of non-empty subsets of nums whose bitwise OR is the maximum achievable.

Two subsets are different when they use different index sets, even if the values coincide.

Example 1

Input: nums = [3,1]
Output: 2
Explanation: The maximum OR is 3, reached by {3} and {3,1}.

Example 2

Input: nums = [2,2,2]
Output: 7
Explanation: Every non-empty subset ORs to 2.

Example 3

Input: nums = [3,2,1,5]
Output: 6

Constraints

  • 1 <= nums.length <= 16
  • 1 <= nums[i] <= 100000

Hints for Count Number of Maximum Bitwise-OR Subsets

  1. Hint 1

    OR only grows, so the maximum is the OR of the whole array.

  2. Hint 2

    With at most 16 elements there are fewer than 65536 subsets — just enumerate them.

  3. Hint 3

    A bitmask over the indices is the cleanest way to enumerate.

How to solve Count Number of Maximum Bitwise-OR Subsets

The best OR is the OR of everything, since adding elements never clears a bit. Counting the subsets that reach it is then a brute-force enumeration over the 2^n - 1 non-empty index masks.

Approach

  1. Compute best, the OR of all elements.
  2. For each mask from 1 to 2^n - 1, OR together the selected elements.
  3. Count the masks whose OR equals best.

Why it works

Bitwise OR is monotone under adding elements, so no subset can exceed the full-array OR, and the full array itself attains it. With n <= 16 the enumeration is at most about a million operations.

Complexity

  • Time — O(2^n · n)
  • Space — O(1)

Pitfalls

  • Starting the mask at 0 counts the empty subset, which the statement excludes.
  • 1 << n with n = 16 is fine, but the loop bound must be exclusive.
  • Recomputing the OR from scratch per mask is fine here; the O(2^n) refinement carries it incrementally.

Reference solution

Python

from typing import List

def countMaxOrSubsets(nums: List[int]) -> int:
    best = 0
    for x in nums:
        best |= x
    n = len(nums)
    count = 0
    for mask in range(1, 1 << n):
        acc = 0
        for i in range(n):
            if (mask >> i) & 1:
                acc |= nums[i]
        if acc == best:
            count += 1
    return count

Java

public static int countMaxOrSubsets(int[] nums) {
    int best = 0;
    for (int x : nums) best |= x;
    int n = nums.length, count = 0;
    for (int mask = 1; mask < (1 << n); mask++) {
        int acc = 0;
        for (int i = 0; i < n; i++) {
            if (((mask >> i) & 1) == 1) acc |= nums[i];
        }
        if (acc == best) count++;
    }
    return count;
}

C++

int countMaxOrSubsets(vector<int>& nums) {
    int best = 0;
    for (int x : nums) best |= x;
    int n = (int) nums.size(), count = 0;
    for (int mask = 1; mask < (1 << n); mask++) {
        int acc = 0;
        for (int i = 0; i < n; i++) {
            if ((mask >> i) & 1) acc |= nums[i];
        }
        if (acc == best) count++;
    }
    return count;
}

JavaScript

var countMaxOrSubsets = function(nums) {
    var best = 0;
    for (var i = 0; i < nums.length; i++) best |= nums[i];
    var n = nums.length, count = 0;
    for (var mask = 1; mask < (1 << n); mask++) {
        var acc = 0;
        for (var j = 0; j < n; j++) {
            if ((mask >> j) & 1) acc |= nums[j];
        }
        if (acc === best) count++;
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 146 bit manipulation problems · the whole catalogue

Learn the technique: Bit Manipulation · Backtracking