LeetCode 0898. Bitwise ORs of Subarrays Solution in Java, C++, Python & More | Explanation + Code

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 * 104
• 0 <= arr[i] <= 109

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 × log M), and the space complexity is O(n × log M). Here, n and M are the length of the array and the maximum value in the array, respectively.

PythonJavaC++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)(code-box)

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(); } }(code-box)

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(); } };(code-box)

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) }(code-box)

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; }(code-box)