Count Number of Maximum Bitwise-OR Subsets

Count Number of Maximum Bitwise-OR Subsets - Problem

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).

Input & Output

Example 1 — Basic Case

$ Input: nums = [3,1]

› Output: 2

💡 Note: Maximum OR is 3|1 = 3. Subsets [3] and [3,1] both achieve OR = 3, so return 2.

Example 2 — Single Element

$ Input: nums = [2,2,2]

› Output: 7

💡 Note: Maximum OR is 2. All non-empty subsets ([2], [2], [2], [2,2], [2,2], [2,2], [2,2,2]) achieve OR = 2.

Example 3 — Different Bits

$ Input: nums = [3,2,1,5]

› Output: 6

💡 Note: Maximum OR is 3|2|1|5 = 7. Count all subsets that achieve OR = 7.

Constraints

1 ≤ nums.length ≤ 16
1 ≤ nums[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array [3,1] with elements to form subsets

Find Max OR

Maximum OR = 3|1 = 3 (all bits from all elements)

Count Subsets

Count subsets with OR = 3: [3] and [3,1]

Key Takeaway

🎯 Key Insight: Maximum OR is achieved by ORing all elements, then count subsets with this value

Asked in

M Microsoft 15 G Google 12

The key insight is to first calculate the maximum possible OR by ORing all elements, then count subsets that achieve this maximum. The backtracking approach explores all possibilities efficiently. Time: O(2ⁿ), Space: O(n) for recursion stack.

Common Approaches

Approach	Time	Space	Notes
✓ Optimized with Bit Analysis	O(2ⁿ)	O(n)	Calculate maximum OR first, then use dynamic programming approach
Brute Force - Generate All Subsets	O(n × 2ⁿ)	O(1)	Generate all possible subsets and check each one's bitwise OR
Backtracking with Pruning	O(2ⁿ)	O(n)	Use DFS to explore all subsets with early termination

Optimized with Bit Analysis — Algorithm Steps

Calculate maximum OR (OR of all elements)
Use bit manipulation to count contributing elements
Apply combinatorial counting for subsets
Handle edge cases efficiently

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Max OR

First determine maximum possible OR value

Memoized DFS

Cache results to avoid recalculating same states

Count Results

Return count of subsets achieving maximum OR

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_STATES 10000

struct MemoEntry {
    int index;
    int currentOr;
    int result;
};

struct MemoEntry memoTable[MAX_STATES];
int memoCount = 0;
int maxOr;

int findMemo(int index, int currentOr) {
    for (int i = 0; i < memoCount; i++) {
        if (memoTable[i].index == index && memoTable[i].currentOr == currentOr) {
            return memoTable[i].result;
        }
    }
    return -1;
}

void addMemo(int index, int currentOr, int result) {
    if (memoCount < MAX_STATES) {
        memoTable[memoCount].index = index;
        memoTable[memoCount].currentOr = currentOr;
        memoTable[memoCount].result = result;
        memoCount++;
    }
}

int countSubsets(int* nums, int n, int index, int currentOr) {
    if (index == n) {
        return currentOr == maxOr ? 1 : 0;
    }
    
    int memoResult = findMemo(index, currentOr);
    if (memoResult != -1) {
        return memoResult;
    }
    
    // Two choices: include or exclude current element
    int result = countSubsets(nums, n, index + 1, currentOr);  // Exclude
    result += countSubsets(nums, n, index + 1, currentOr | nums[index]);  // Include
    
    addMemo(index, currentOr, result);
    return result;
}

int solution(int* nums, int n) {
    // Calculate maximum possible OR
    maxOr = 0;
    for (int i = 0; i < n; i++) {
        maxOr |= nums[i];
    }
    
    memoCount = 0;
    
    // Subtract 1 to exclude empty subset
    return countSubsets(nums, n, 0, 0) - 1;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for array format [1,2,3]
    int nums[20];
    int n = 0;
    char* ptr = strchr(line, '[') + 1;
    char* token = strtok(ptr, ",]");
    
    while (token != NULL && n < 20) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ)

Still need to consider all subset combinations in worst case

✓ Linear Growth

Space Complexity

O(n)

Recursion stack and memoization table

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized with Bit Analysis — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler