2044. Count Number of Maximum Bitwise-OR Subsets

Description

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⁵

Solutions

Solution 1: DFS

Thinking

With \(n \le 16\) there are \(2^{16}\) subsets. The OR of all elements is the maximum \(mx\); we count subsets whose OR equals \(mx\).

DFS includes or skips each index and compares the running OR at the leaves. Depth \(n\), no explicit mask list.

The maximum bitwise OR value \(\textit{mx}\) in the array \(\textit{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 \(\textit{mx}\). We design a function \(\text{dfs(i, t)}\), which represents the number of subsets starting from index \(\textit{i}\) with the current bitwise OR value being \(\textit{t}\). Initially, \(\textit{i} = 0\) and \(\textit{t} = 0\).

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

Python3JavaC++GoTypeScriptRust

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        def dfs(i, t):
            nonlocal ans, mx
            if i == len(nums):
                if t == mx:
                    ans += 1
                return
            dfs(i + 1, t)
            dfs(i + 1, t | nums[i])

        ans = 0
        mx = reduce(lambda x, y: x | y, nums)
        dfs(0, 0)
        return ans

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]);
    }
}

class Solution {
public:
    int countMaxOrSubsets(vector<int>& nums) {
        int ans = 0;
        int mx = accumulate(nums.begin(), nums.end(), 0, bit_or<int>());
        auto dfs = [&](this auto&& dfs, int i, int t) {
            if (i == nums.size()) {
                if (t == mx) {
                    ans++;
                }
                return;
            }
            dfs(i + 1, t);
            dfs(i + 1, t | nums[i]);
        };
        dfs(0, 0);
        return ans;
    }
};

func countMaxOrSubsets(nums []int) (ans int) {
    mx := 0
    for _, x := range nums {
        mx |= x
    }

    var dfs func(i, t int)
    dfs = func(i, t int) {
        if i == len(nums) {
            if t == mx {
                ans++
            }
            return
        }
        dfs(i+1, t)
        dfs(i+1, t|nums[i])
    }

    dfs(0, 0)
    return
}

function countMaxOrSubsets(nums: number[]): number {
    let ans = 0;
    const mx = nums.reduce((x, y) => x | y, 0);

    const dfs = (i: number, t: number) => {
        if (i === nums.length) {
            if (t === mx) {
                ans++;
            }
            return;
        }
        dfs(i + 1, t);
        dfs(i + 1, t | nums[i]);
    };

    dfs(0, 0);
    return ans;
}

impl Solution {
    pub fn count_max_or_subsets(nums: Vec<i32>) -> i32 {
        let mut ans = 0;
        let mx = nums.iter().fold(0, |x, &y| x | y);

        fn dfs(i: usize, t: i32, nums: &Vec<i32>, mx: i32, ans: &mut i32) {
            if i == nums.len() {
                if t == mx {
                    *ans += 1;
                }
                return;
            }
            dfs(i + 1, t, nums, mx, ans);
            dfs(i + 1, t | nums[i], nums, mx, ans);
        }

        dfs(0, 0, &nums, mx, &mut ans);
        ans
    }
}

Solution 2: Binary Enumeration

Thinking

Solution 1 is recursive. Binary enumeration ORs bits of each mask while updating the running maximum and its count, so \(mx\) need not be known in advance.

The inner scan costs an extra \(n\); extra memory drops to \(O(1)\).

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

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

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

Python3JavaC++GoTypeScriptRust

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        mx = 0
        for mask in range(1 << n):
            t = 0
            for i, v in enumerate(nums):
                if (mask >> i) & 1:
                    t |= v
            if mx < t:
                mx = t
                ans = 1
            elif mx == t:
                ans += 1
        return ans

class Solution {
    public int countMaxOrSubsets(int[] nums) {
        int n = nums.length;
        int ans = 0;
        int mx = 0;
        for (int mask = 1; mask < 1 << n; ++mask) {
            int t = 0;
            for (int i = 0; i < n; ++i) {
                if (((mask >> i) & 1) == 1) {
                    t |= nums[i];
                }
            }
            if (mx < t) {
                mx = t;
                ans = 1;
            } else if (mx == t) {
                ++ans;
            }
        }
        return ans;
    }
}

class Solution {
public:
    int countMaxOrSubsets(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        int mx = 0;
        for (int mask = 1; mask < 1 << n; ++mask) {
            int t = 0;
            for (int i = 0; i < n; ++i) {
                if ((mask >> i) & 1) {
                    t |= nums[i];
                }
            }
            if (mx < t) {
                mx = t;
                ans = 1;
            } else if (mx == t)
                ++ans;
        }
        return ans;
    }
};

func countMaxOrSubsets(nums []int) (ans int) {
    n := len(nums)
    mx := 0

    for mask := 0; mask < (1 << n); mask++ {
        t := 0
        for i, v := range nums {
            if (mask>>i)&1 == 1 {
                t |= v
            }
        }
        if mx < t {
            mx = t
            ans = 1
        } else if mx == t {
            ans++
        }
    }

    return
}

function countMaxOrSubsets(nums: number[]): number {
    const n = nums.length;
    let ans = 0;
    let mx = 0;

    for (let mask = 0; mask < 1 << n; mask++) {
        let t = 0;
        for (let i = 0; i < n; i++) {
            if ((mask >> i) & 1) {
                t |= nums[i];
            }
        }
        if (mx < t) {
            mx = t;
            ans = 1;
        } else if (mx === t) {
            ans++;
        }
    }

    return ans;
}

impl Solution {
    pub fn count_max_or_subsets(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut ans = 0;
        let mut mx = 0;

        for mask in 0..(1 << n) {
            let mut t = 0;
            for i in 0..n {
                if (mask >> i) & 1 == 1 {
                    t |= nums[i];
                }
            }
            if mx < t {
                mx = t;
                ans = 1;
            } else if mx == t {
                ans += 1;
            }
        }

        ans
    }
}

2044. Count Number of Maximum Bitwise-OR Subsets

Description

Solutions

Solution 1: DFS

Solution 2: Binary Enumeration

Comments