algoadvance

Leetcode 898. Bitwise ORs of Subarrays

Problem Statement

Given an array arr of integers, find the number of unique results from all possible bitwise OR operations of subarrays.

Example:

Input: arr = [1,1,2]
Output: 3
Explanation: The possible subarrays are [1], [1], [2], [1,1], [1,2], [1,1,2]. The results of these OR operations are:
1 = 1
1 = 1
2 = 2
1 | 1 = 1
1 | 2 = 3
1 | 1 | 2 = 3
There are 3 unique values, so the answer is 3.

Clarifying Questions

  1. Can the array be empty? No, the array will have at least one element.
  2. What are the constraints on the array size and element values? The array length can be up to 50, and element values range from 0 to (10^9).

Strategy

  1. Initialization: Use two sets:
    • cur: To store the results of OR operations ending at the current index.
    • res: To store all unique OR results.

  2. Iteration: For each element in the array, update the cur set to include results of OR operations combining the current element with all previous subarray results. Add all results to res.

  3. Updating ORs: For each element arr[i]:
    • Initialize new_cur set with arr[i].
    • For each element in the current cur, compute the OR operation with arr[i] and add to new_cur.
    • After processing arr[i], set cur to new_cur.

  4. Unique Results: Insert the results of new_cur into the res set.

  5. Final Result: The size of the res set will be the number of unique OR results.

Time Complexity

Code

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public int subarrayBitwiseORs(int[] arr) {
        Set<Integer> res = new HashSet<>();
        Set<Integer> cur = new HashSet<>();
        
        for (int num : arr) {
            Set<Integer> newCur = new HashSet<>();
            newCur.add(num);
            for (int x : cur) {
                newCur.add(num | x);
            }
            cur = newCur;
            res.addAll(cur);
        }
        
        return res.size();
    }
}

Explanation

  1. We use two sets, res (to store all unique OR results) and cur (to store OR results ending with the current element).
  2. For each element in the array, we calculate the new set of OR results by performing the OR operation between the current element and each element in the cur set from the previous iteration.
  3. Update the cur set with these new OR results.
  4. Add all results from cur to res.
  5. Finally, return the size of the res set, which represents the number of unique OR results.

This approach ensures we efficiently track all unique results without redundant computations.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI