Problem

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.

Examples

Example 1

1
2
3

Input: arr = [0]
Output: 1
Explanation: There is only one possible result: 0.

Example 2

1
2
3
4
5

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

1
2
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 * 10^4
  • 0 <= arr[i] <= 10^9

Solution

Method 1 – Dynamic Programming with Sets

Intuition

The key idea is to keep track of all possible bitwise OR results for subarrays ending at each position. Since OR is monotonic (adding more elements can only set more bits), the number of unique results per step is manageable. By iteratively updating the set of ORs for each subarray ending at the current index, we can efficiently collect all unique OR values.

Approach

  1. Initialize an empty set ans to store all unique OR results.
  2. Initialize an empty set cur to store OR results for subarrays ending at the previous index.
  3. For each element x in the array:
  • Create a new set nxt to store OR results for subarrays ending at the current index.
  • For each value y in cur, add y | x to nxt.
  • Add x itself to nxt (subarray of length 1).
  • Update cur to nxt.
  • Add all values in cur to ans.
  1. Return the size of ans as the answer.

This approach efficiently avoids recomputation and leverages set properties to ensure uniqueness.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
   int subarrayBitwiseORs(vector<int>& arr) {
      unordered_set<int> ans, cur;
      for (int x : arr) {
        unordered_set<int> nxt = {x};
        for (int y : cur) nxt.insert(y | x);
        cur = nxt;
        ans.insert(cur.begin(), cur.end());
      }
      return ans.size();
   }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func subarrayBitwiseORs(arr []int) int {
   ans := map[int]struct{}{}
   cur := map[int]struct{}{}
   for _, x := range arr {
      nxt := map[int]struct{}{x: {}}
      for y := range cur {
        nxt[y|x] = struct{}{}
      }
      cur = nxt
      for v := range cur {
        ans[v] = struct{}{}
      }
   }
   return len(ans)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
   public int subarrayBitwiseORs(int[] arr) {
      Set<Integer> ans = new HashSet<>(), cur = new HashSet<>();
      for (int x : arr) {
        Set<Integer> nxt = new HashSet<>();
        nxt.add(x);
        for (int y : cur) nxt.add(y | x);
        cur = nxt;
        ans.addAll(cur);
      }
      return ans.size();
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
   fun subarrayBitwiseORs(arr: IntArray): Int {
      val ans = mutableSetOf<Int>()
      var cur = mutableSetOf<Int>()
      for (x in arr) {
        val nxt = mutableSetOf(x)
        for (y in cur) nxt.add(y or x)
        cur = nxt
        ans.addAll(cur)
      }
      return ans.size
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
   def subarrayBitwiseORs(self, arr: list[int]) -> int:
      ans: set[int] = set()
      cur: set[int] = set()
      for x in arr:
        nxt = {x}
        for y in cur:
           nxt.add(y | x)
        cur = nxt
        ans |= cur
      return len(ans)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
   pub fn subarray_bitwise_ors(arr: Vec<i32>) -> i32 {
      use std::collections::HashSet;
      let mut ans = HashSet::new();
      let mut cur = HashSet::new();
      for &x in &arr {
        let mut nxt = HashSet::new();
        nxt.insert(x);
        for &y in &cur {
           nxt.insert(y | x);
        }
        cur = nxt;
        for &v in &cur {
           ans.insert(v);
        }
      }
      ans.len() as i32
   }
}

Complexity

  • ⏰ Time complexity: O(N * 32) (since each number is up to 32 bits, and the number of unique ORs per step is limited)
  • 🧺 Space complexity: O(N * 32) (for storing unique OR results)