Count Number of Maximum Bitwise-OR Subsets - Solution & Explanation

Q: Is Count Number of Maximum Bitwise-OR Subsets easy or hard?

The problem is categorized as Medium on LeetCode. The implementation is straightforward once you recognize that the maximum OR equals the OR of all elements. The main challenge is efficiently enumerating subsets using backtracking or bitmasking.

Q: Count Number of Maximum Bitwise-OR Subsets Python/Java solution

In Python or Java, compute the target OR by OR-ing all elements in the array. Then generate subsets using recursion or iterate through bitmasks from 0 to (1 << n) - 1. For each subset, calculate the OR and increase the counter if it equals the maximum. Both implementations run in O(2^n) time.

Q: How to solve Count Number of Maximum Bitwise-OR Subsets in O(n)?

An O(n) solution does not exist because the problem inherently requires examining subsets. The optimal strategy enumerates all 2^n subsets and checks their OR values. The typical implementation uses backtracking or bitmask enumeration, giving O(2^n) time complexity.

Q: What is the best approach for Count Number of Maximum Bitwise-OR Subsets?

The most practical approach is subset enumeration using backtracking. First compute the maximum OR by OR-ing all numbers in the array. Then recursively generate all subsets while tracking the running OR value. Whenever the OR equals the target maximum, increment the count. The algorithm runs in O(2^n) time with O(n) recursion stack space.

Q: Is Count Number of Maximum Bitwise-OR Subsets asked at Google/Amazon/Meta?

Bit manipulation and subset enumeration problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variations of subset OR, AND, or XOR enumeration are common because they test understanding of recursion, bit operations, and combinatorial reasoning.

Q: What data structure is used in Count Number of Maximum Bitwise-OR Subsets?

The solution mainly relies on arrays and bitwise operations rather than complex data structures. Backtracking uses the call stack to explore subsets, while the iterative method uses integer bitmasks to represent subsets.

Q: What is the time complexity of Count Number of Maximum Bitwise-OR Subsets?

The time complexity is O(2^n) because every subset of the array must be evaluated. With recursive enumeration, each subset is processed once and only a constant-time OR operation is applied at each step. Space complexity is O(n) due to the recursion depth.

MediumArray Backtracking Bit Manipulation Enumeration25 min readAsked at: Amazon, Microsoft, Meta +4

Practice this problem

Problem Statement

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 2³ - 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] <= 10⁵

Approach Overview

Problem Overview: You get an integer array nums. Every subset produces a bitwise OR value. The task is to compute the maximum possible OR across all subsets and count how many subsets produce that exact value.

The key observation: the maximum OR is simply the OR of all elements in the array. Any subset that produces the same value contributes to the final count. The problem therefore reduces to enumerating subsets and checking whether their OR equals this maximum.

Approach 1: Recursive Enumeration with Backtracking (O(2^n) time, O(n) space)

This approach explores every subset using recursion. At each index you choose whether to include the current number or skip it. While traversing, maintain the running OR value. Before recursion starts, compute the target OR by OR-ing every element in the array. During traversal, whenever the recursion reaches the end of the array, compare the accumulated OR with the target. If they match, increment the counter.

This method fits naturally with backtracking. Each recursive branch represents one subset. The recursion depth is at most n, so the auxiliary stack space is O(n). Since all subsets are explored, the total number of states is 2^n. This approach is easy to reason about and works well for the constraint size used in this problem.

Approach 2: Iterative Bitmasking Enumeration (O(2^n * n) time, O(1) space)

Instead of recursion, represent subsets using bitmasks. For an array of size n, every integer from 0 to (1 << n) - 1 represents a subset. If the i-th bit in the mask is set, include nums[i] in the subset. For each mask, iterate through bits and compute the OR value of the chosen elements.

After calculating the OR for that mask, compare it with the precomputed maximum OR. If they match, increment the answer. This method relies heavily on bit manipulation and explicit subset enumeration. The algorithm checks 2^n masks and may scan up to n bits per mask, resulting in O(2^n * n) time. Space usage stays constant since no recursion stack is needed.

Recommended for interviews: Recursive enumeration is usually preferred. It demonstrates comfort with subset generation and backtracking patterns. Interviewers expect you to first recognize that the maximum OR equals the OR of all elements, then enumerate subsets while tracking OR values. Bitmasking shows strong understanding of binary subset representation and is often presented as an alternative implementation.

Approach 1: Recursive Enumeration with Bitmasking

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.

This solution uses a recursive helper function countMaxOrSubsets which explores all possible subsets of the input array by deciding whether to include each element in the current subset. The function keeps track of the current subset’s bitwise OR and updates the global maximum OR and corresponding count of subsets achieving this OR as necessary.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Iterative Bitmasking

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.

The C solution iteratively calculates OR values for subsets encoded through bitmasks, iterating through possible subset representations and dynamically including elements based on bit positions, updating the maximum OR and associated subset count as it runs.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: DFS

The maximum bitwise OR value mx in the array nums can be obtained by performing bitwise OR on all elements in the array.

Then we can use depth-first search to enumerate all subsets and count the number of subsets whose bitwise OR equals mx. We design a function dfs(i, t), which represents the number of subsets starting from index i with the current bitwise OR value being t. Initially, i = 0 and t = 0.

In the function dfs(i, t), if i equals the array length, it means we have enumerated all elements. At this point, if t equals mx, we increment the answer by one. Otherwise, we can choose to either exclude the current element nums[i] or include the current element nums[i], so we can recursively call dfs(i + 1, t) and dfs(i + 1, t | nums[i]).

Finally, we return the answer.

The time complexity is O(2^n), and the space complexity is O(n), where n is the length of the array nums.

Code

Python Java C++Go TypeScript Rust

Python

Java

C++

TypeScript

Rust

Try this approach in the editor →

Approach 4: Binary Enumeration

We can use binary enumeration to count the bitwise OR results of all subsets. For an array nums of length n, we can use an integer mask to represent a subset, where the i-th bit of mask being 1 means including element nums[i], and 0 means not including it.

We can iterate through all possible mask values from 0 to 2^n - 1. For each mask, we can calculate the bitwise OR result of the corresponding subset and update the maximum value mx and answer ans.

The time complexity is O(2^n cdot n), where n is the length of the array nums. The space complexity is O(1).

Code

Python Java C++Go TypeScript Rust

Python

Java

C++

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Recursive Enumeration with Bitmasking	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.
Iterative Bitmasking	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.
DFS	—
Binary Enumeration	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Recursive Enumeration with Backtracking	O(2^n)	O(n)	Best for interviews and when demonstrating subset recursion patterns
Iterative Bitmasking	O(2^n * n)	O(1)	Useful when you prefer iterative subset generation with bit operations

Video Solution

Count Number of Maximum Bitwise-OR Subsets | Simplest Approach | Leetcode 2044 | codestorywithMIK • codestorywithMIK • 14,203 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Count Number of Maximum Bitwise-OR Subsets easy or hard?

The problem is categorized as Medium on LeetCode. The implementation is straightforward once you recognize that the maximum OR equals the OR of all elements. The main challenge is efficiently enumerating subsets using backtracking or bitmasking.

Count Number of Maximum Bitwise-OR Subsets Python/Java solution

In Python or Java, compute the target OR by OR-ing all elements in the array. Then generate subsets using recursion or iterate through bitmasks from 0 to (1 << n) - 1. For each subset, calculate the OR and increase the counter if it equals the maximum. Both implementations run in O(2^n) time.

How to solve Count Number of Maximum Bitwise-OR Subsets in O(n)?

An O(n) solution does not exist because the problem inherently requires examining subsets. The optimal strategy enumerates all 2^n subsets and checks their OR values. The typical implementation uses backtracking or bitmask enumeration, giving O(2^n) time complexity.

What is the best approach for Count Number of Maximum Bitwise-OR Subsets?

The most practical approach is subset enumeration using backtracking. First compute the maximum OR by OR-ing all numbers in the array. Then recursively generate all subsets while tracking the running OR value. Whenever the OR equals the target maximum, increment the count. The algorithm runs in O(2^n) time with O(n) recursion stack space.

Is Count Number of Maximum Bitwise-OR Subsets asked at Google/Amazon/Meta?

Bit manipulation and subset enumeration problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variations of subset OR, AND, or XOR enumeration are common because they test understanding of recursion, bit operations, and combinatorial reasoning.

What data structure is used in Count Number of Maximum Bitwise-OR Subsets?

The solution mainly relies on arrays and bitwise operations rather than complex data structures. Backtracking uses the call stack to explore subsets, while the iterative method uses integer bitmasks to represent subsets.

What is the time complexity of Count Number of Maximum Bitwise-OR Subsets?

The time complexity is O(2^n) because every subset of the array must be evaluated. With recursive enumeration, each subset is processed once and only a constant-time OR operation is applied at each step. Space complexity is O(n) due to the recursion depth.

Ready to solve this problem?

Practice Count Number of Maximum Bitwise-OR Subsets with our built-in code editor and test cases.

Practice on FleetCode

Largest Combination With Bitwise AND Greater Than Zero

Longest Subarray With Maximum Bitwise AND

Problem Info

DifficultyMedium

Acceptance89.5%

Approaches4

Reading time25 min

Asked at

Amazon Microsoft Meta BNY Mellon Google

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Recursive Enumeration with Bitmasking

Code

Complexity

Approach 2: Iterative Bitmasking

Code

Complexity

Approach 3: DFS

Code

Approach 4: Binary Enumeration

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents