algoadvance

Leetcode 898. Bitwise ORs of Subarrays

Problem Statement

The problem is to find the number of distinct values that can be obtained by performing bitwise OR on all subarrays of a given array.

Example:

Input:

A = [1, 2, 4]

Output:

6

Explanation: The subarrays are [1], [1, 2], [1, 2, 4], [2], [2, 4], [4]. Their corresponding bitwise ORs are 1, 3, 7, 2, 6, 4. The distinct values are: 1, 2, 3, 4, 6, 7.

Clarifying Questions

1. What is the range of the length of array ( A )?
   • The length ( n ) of the array can go up to 5000.
2. What are the constraints on the values within the array ( A )?
   • The values within the array are non-negative integers and within the range [0, 10^9].
3. Is performance a concern due to potentially large values in the input array?
   • Yes, performance is a key factor since the size of the array can be up to 5000, making a direct brute-force approach inefficient.

Strategy

1. Data Structures:
   • Use a set to keep track of all distinct values obtained by bitwise OR operations on subarrays.
   • Use two additional sets to keep track of current OR values and new OR values generated in each iteration.
2. Logic:
   • Iterate through each element in the array.
   • For each element, update the new set of OR values by OR-ing the current element with each element in the current set of OR values.
   • Also, add the element itself to cater to single-element subarrays.
   • Update the overall set of distinct OR values.
3. Optimization Considerations:
   • Using sets ensures that only unique values are retained without duplicates.
   • This approach minimizes redundant computations compared to checking every possible subarray individually.

Code

Here’s the implementation of the above strategy in C++:

#include <vector>
#include <unordered_set>

int subarrayBitwiseORs(std::vector<int>& A) {
    std::unordered_set<int> res;
    std::unordered_set<int> cur;
    
    for (int num : A) {
        std::unordered_set<int> next;
        next.insert(num);
        
        for (int val : cur) {
            next.insert(num | val);
        }
        
        cur = std::move(next);
        
        for (int val : cur) {
            res.insert(val);
        }
    }
    
    return res.size();
}

Explanation:

• Initialize res to store all distinct OR results and cur to store current OR results.
• For every number num in the array:
  • Create a new set next and initialize it with num (this handles the single-element subarray case).
  • For each value in cur, compute the OR with num and add it to next.
  • Update cur to be next, effectively shifting the currently considered subarray window.
  • Add all values in cur to the result set res.
• At the end, res contains all distinct OR values from subarrays.

Time Complexity:

The time complexity of this approach is as follows:

• Let ( n ) be the length of the array.
• In the worst case, every OR operation results in a new unique value, leading to ( O(n^2) ) overall operations because each number can be involved in multiple subarray OR computations.

Thus, the overall time complexity is approximately ( O(n^2) ). This should be efficient enough for ( n ) up to 5000.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?