2044. Count Number of Maximum Bitwise-OR Subsets LeetCode Solution

In this guide, you will get 2044. Count Number of Maximum Bitwise-OR Subsets LeetCode Solution with the best time and space complexity. The solution to Count Number of Maximum Bitwise-OR Subsets problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Count Number of Maximum Bitwise-OR Subsets solution in C++
Count Number of Maximum Bitwise-OR Subsets solution in Java
Count Number of Maximum Bitwise-OR Subsets solution in Python
Additional Resources

2044. Count Number of Maximum Bitwise-OR Subsets LeetCode Solution image

Problem Statement of Count Number of Maximum Bitwise-OR Subsets

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

Complexity Analysis

Time Complexity: O(2^n)
Space Complexity: O(2^n)

2044. Count Number of Maximum Bitwise-OR Subsets LeetCode Solution in C++

class Solution {
 public:
  int countMaxOrSubsets(vector<int>& nums) {
    const int ors = accumulate(nums.begin(), nums.end(), 0, bit_or<>());
    int ans = 0;
    dfs(nums, 0, 0, ors, ans);
    return ans;
  }

 private:
  void dfs(const vector<int>& nums, int i, int path, const int& ors, int& ans) {
    if (i == nums.size()) {
      if (path == ors)
        ++ans;
      return;
    }

    dfs(nums, i + 1, path, ors, ans);
    dfs(nums, i + 1, path | nums[i], ors, ans);
  }
};
/* code provided by PROGIEZ */

2044. Count Number of Maximum Bitwise-OR Subsets LeetCode Solution in Java

class Solution {
  public int countMaxOrSubsets(int[] nums) {
    final int ors = Arrays.stream(nums).reduce((a, b) -> a | b).getAsInt();
    dfs(nums, 0, 0, ors);
    return ans;
  }

  private int ans = 0;

  private void dfs(int[] nums, int i, int path, final int ors) {
    if (i == nums.length) {
      if (path == ors)
        ++ans;
      return;
    }

    dfs(nums, i + 1, path, ors);
    dfs(nums, i + 1, path | nums[i], ors);
  }
}
// code provided by PROGIEZ

2044. Count Number of Maximum Bitwise-OR Subsets LeetCode Solution in Python

class Solution:
  def countMaxOrSubsets(self, nums: list[int]) -> int:
    ors = functools.reduce(operator.or_, nums)
    ans = 0

    def dfs(i: int, path: int) -> None:
      nonlocal ans
      if i == len(nums):
        if path == ors:
          ans += 1
        return

      dfs(i + 1, path)
      dfs(i + 1, path | nums[i])

    dfs(0, 0)
    return ans
 # code by PROGIEZ