Welcome to Subscribe On Youtube

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 * 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 \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.

  • class Solution {
        public int subarrayBitwiseORs(int[] arr) {
            Set<Integer> s = new HashSet<>();
            s.add(0);
            Set<Integer> ans = new HashSet<>();
            for (int x : arr) {
                Set<Integer> t = new HashSet<>();
                for (int y : s) {
                    t.add(x | y);
                }
                t.add(x);
                s = t;
                ans.addAll(s);
            }
            return ans.size();
        }
    }
    
  • class Solution {
    public:
        int subarrayBitwiseORs(vector<int>& arr) {
            unordered_set<int> s{ {0} };
            unordered_set<int> ans;
            for (int& x : arr) {
                unordered_set<int> t{ {x} };
                for (int y : s) {
                    t.insert(x | y);
                }
                s = move(t);
                ans.insert(s.begin(), s.end());
            }
            return ans.size();
        }
    };
    
  • class Solution:
        def subarrayBitwiseORs(self, arr: List[int]) -> int:
            s = {0}
            ans = set()
            for x in arr:
                s = {x | y for y in s} | {x}
                ans |= s
            return len(ans)
    
    
  • func subarrayBitwiseORs(arr []int) int {
    	ans := map[int]bool{}
    	s := map[int]bool{0: true}
    	for _, x := range arr {
    		t := map[int]bool{x: true}
    		for y := range s {
    			t[x|y] = true
    		}
    		s = t
    		for y := range s {
    			ans[y] = true
    		}
    	}
    	return len(ans)
    }
    
  • function subarrayBitwiseORs(arr: number[]): number {
        const s: Set<number> = new Set();
        const ans: Set<number> = new Set();
        for (const x of arr) {
            const t: Set<number> = new Set();
            for (const y of s) {
                t.add(x | y);
            }
            t.add(x);
            s.clear();
            for (const y of t) {
                s.add(y);
                ans.add(y);
            }
        }
        return ans.size;
    }
    
    

All Problems

All Solutions