Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/898.html
898. Bitwise ORs of Subarrays
Level
Medium
Description
We have an array A
of non-negative integers.
For every (contiguous) subarray B = [A[i], A[i+1], ..., A[j]]
(with i <= j
), we take the bitwise OR of all the elements in B
, obtaining a result A[i] | A[i+1] | ... | A[j]
.
Return the number of possible results. (Results that occur more than once are only counted once in the final answer.)
Example 1:
Input: [0]
Output: 1
Explanation:
There is only one possible result: 0.
Example 2:
Input: [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: [1,2,4]
Output: 6
Explanation:
The possible results are 1, 2, 3, 4, 6, and 7.
Note:
1 <= A.length <= 50000
0 <= A[i] <= 10^9
Solution
Use a set to store all different bitwise OR results and use a list to store the previous bitwise OR results. For each number in A
, add it to the set and the list, and use another list to store the current bitwise OR results. If a bitwise OR result of the current number is greater than the number, then the bitwise OR result is a new result, so add the new result into the second list. After the results of the current number are calculated, assign the second list to the first list. Finally, return the set’s size.
-
class Solution { public int subarrayBitwiseORs(int[] A) { Set<Integer> totalSet = new HashSet<Integer>(); List<Integer> prevList = new ArrayList<Integer>(); int length = A.length; for (int i = 0; i < length; i++) { int num = A[i]; List<Integer> curList = new ArrayList<Integer>(); totalSet.add(num); curList.add(num); for (int prevNum : prevList) { int bitOR = num | prevNum; if (bitOR > num) curList.add(bitOR); totalSet.add(bitOR); num = bitOR; } prevList = new ArrayList<Integer>(curList); } return totalSet.size(); } }
-
// OJ: https://leetcode.com/problems/bitwise-ors-of-subarrays/ // Time: O(30N) // Space: O(30N) class Solution { public: int subarrayBitwiseORs(vector<int>& A) { unordered_set<int> all, cur, next; for (int n : A) { next.clear(); next.insert(n); for (int prev : cur) next.insert(prev | n); for (int m : next) all.insert(m); swap(cur, next); } return all.size(); } };
-
class Solution: def subarrayBitwiseORs(self, arr: List[int]) -> int: s = set() prev = 0 for i, v in enumerate(arr): prev |= v curr = 0 for j in range(i, -1, -1): curr |= arr[j] s.add(curr) if curr == prev: break return len(s) ############ class Solution(object): def subarrayBitwiseORs(self, A): """ :type A: List[int] :rtype: int """ res = set() cur = set() for a in A: cur = {n | a for n in cur} | {a} res |= cur return len(res)
-
func subarrayBitwiseORs(arr []int) int { s := map[int]bool{} prev := 0 for i, v := range arr { prev |= v curr := 0 for j := i; j >= 0; j-- { curr |= arr[j] s[curr] = true if curr == prev { break } } } return len(s) }