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. 1 <= A.length <= 50000
  2. 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)

All Problems

All Solutions