898. Bitwise ORs of Subarrays

Description

Given an integer array arr, return the number of distinct bitwise ORs of all the non-empty subarrays of arr.

The bitwise OR of a subarray is the bitwise OR of each integer in the subarray. The bitwise OR of a subarray of one integer is that integer.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: arr = [0]
Output: 1
Explanation: There is only one possible result: 0.

Example 2:

Input: arr = [1,1,2]
Output: 3
Explanation: The possible subarrays are [1], [1], [2], [1, 1], [1, 2], [1, 1, 2].
These yield the results 1, 1, 2, 1, 3, 3.
There are 3 unique values, so the answer is 3.

Example 3:

Input: arr = [1,2,4]
Output: 6
Explanation: The possible results are 1, 2, 3, 4, 6, and 7.

Constraints:

1 <= arr.length <= 5 * 10⁴
0 <= arr[i] <= 10⁹

Solutions

Solution 1: Hash Table

The problem asks for the number of unique bitwise OR operations results of subarrays. If we enumerate the end position \(i\) of the subarray, the number of bitwise OR operations results of the subarray ending at \(i-1\) does not exceed \(32\). This is because the bitwise OR operation is a monotonically increasing operation.

Therefore, we use a hash table \(ans\) to record all the results of the bitwise OR operations of subarrays, and a hash table \(s\) to record the results of the bitwise OR operations of subarrays ending with the current element. Initially, \(s\) only contains one element \(0\).

Next, we enumerate the end position \(i\) of the subarray. The result of the bitwise OR operation of the subarray ending at \(i\) is the set of results of the bitwise OR operation of the subarray ending at \(i-1\) and \(a[i]\), plus \(a[i]\) itself. We use a hash table \(t\) to record the results of the bitwise OR operation of the subarray ending at \(i\), then we update \(s = t\), and add all elements in \(t\) to \(ans\).

Finally, we return the number of elements in the hash table \(ans\).

The time complexity is \(O(n \times \log M)\), and the space complexity is \(O(n \times \log M)\). Here, \(n\) and \(M\) are the length of the array and the maximum value in the array, respectively.

Python3JavaC++GoTypeScript

class Solution:
    def subarrayBitwiseORs(self, arr: List[int]) -> int:
        ans = set()
        s = set()
        for x in arr:
            s = {x | y for y in s} | {x}
            ans |= s
        return len(ans)

class Solution {
    public int subarrayBitwiseORs(int[] arr) {
        Set<Integer> ans = new HashSet<>();
        Set<Integer> s = new HashSet<>();
        for (int x : arr) {
            Set<Integer> t = new HashSet<>();
            for (int y : s) {
                t.add(x | y);
            }
            t.add(x);
            ans.addAll(t);
            s = t;
        }
        return ans.size();
    }
}

class Solution {
public:
    int subarrayBitwiseORs(vector<int>& arr) {
        unordered_set<int> ans;
        unordered_set<int> s;
        for (int x : arr) {
            unordered_set<int> t;
            for (int y : s) {
                t.insert(x | y);
            }
            t.insert(x);
            ans.insert(t.begin(), t.end());
            s = move(t);
        }
        return ans.size();
    }
};

func subarrayBitwiseORs(arr []int) int {
    ans := map[int]bool{}
    s := map[int]bool{}
    for _, x := range arr {
        t := map[int]bool{x: true}
        for y := range s {
            t[x|y] = true
        }
        for y := range t {
            ans[y] = true
        }
        s = t
    }
    return len(ans)
}

function subarrayBitwiseORs(arr: number[]): number {
    const ans: Set<number> = new Set();
    const s: Set<number> = new Set();
    for (const x of arr) {
        const t: Set<number> = new Set([x]);
        for (const y of s) {
            t.add(x | y);
        }
        s.clear();
        for (const y of t) {
            ans.add(y);
            s.add(y);
        }
    }
    return ans.size;
}

898. Bitwise ORs of Subarrays

Description

Solutions

Solution 1: Hash Table

Comments