Today I have done leetcode's July LeetCoding Challenge with cpp.

July LeetCoding Challenge 31

Description

Bitwise ORs of Subarrays

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

Solution

class Solution {
public:
  int subarrayBitwiseORs(vector<int>& A) {
    unordered_set<int> cnt;
    for(int i = 0; i < A.size(); ++i) {
      int pre = 0;
      cnt.insert(A[i]);
      for(int j = i-1; j >= 0 && (pre|A[i]) != pre; --j) {
        pre |= A[j];
        cnt.insert(pre|A[i]);
      }
    }
    return cnt.size();
  }
};

// Accepted
// 85/85 cases passed (275 ms)
// Your runtime beats 96.23 % of cpp submissions
// Your memory usage beats 94.35 % of cpp submissions (106.3 MB)