Problem Statement
Given an integer array arr, find the bitwise OR of every non-empty contiguous subarray. Return the number of different OR values obtained.
A subarray contains one or more neighbouring elements of the array. Bitwise OR keeps a bit set if it is set in at least one of the numbers being combined.
Example 1
Input: arr = [2, 2]
Output: 1
Explanation: The non-empty subarrays [2], [2], and [2, 2] all evaluate to a bitwise OR of 2. So, the answer is 1.
Example 2
Input: arr = [1, 2, 3]
Output: 3
Explanation: The non-empty subarrays [1], [2], [3], [1, 2], [2, 3], and [1, 2, 3] and bitwise OR values are 1, 2, 3, 3, 3, and 3 respectively, giving 3 distinct OR values {1, 2, 3}.
Brute Force Approach
Choose a starting position and grow the subarray one element at a time. Keep its current OR so that adding another element needs only one OR operation.
For example, after finding the OR of [1, 2], we can include the next element by applying OR to the saved value. We do not need to calculate the whole subarray’s OR again.
Repeat this for every starting position. A set stores each result only once, even when several subarrays produce the same value.
Algorithm
Create an empty set to store all distinct bitwise OR values obtained from subarrays, automatically eliminating duplicates.
Traverse the array from left to right, treating each index as the starting position of a subarray.
For each starting position, initialize the running bitwise OR value to zero.
Starting from the current position, extend the subarray one element at a time toward the right.
For each extension, update the running OR value by performing a bitwise OR with the newly included element.
Insert the updated OR value into the set to keep track of all unique results.
After processing every possible subarray, return the number of distinct values stored in the set.
Dry Run
Count Distinct Bitwise OR Values of Subarrays - Brute Force
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the count of distinct bitwise OR values of every subarray. int subarrayBitwiseORs(vector<int>& arr) { // A hash set keeps one copy of each OR value. unordered_set<int> distinct; int n = arr.size(); for (int start = 0; start < n; ++start) { // Each starting position needs a fresh running OR. int currentOR = 0; for (int end = start; end < n; ++end) { // Extend the subarray by one element. currentOR |= arr[end]; distinct.insert(currentOR); } } return distinct.size(); }};// Driver codeint main() { vector<int> arr = {1, 2, 3}; Solution solution; cout << solution.subarrayBitwiseORs(arr) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(N²). Generating N(N + 1) / 2 subarrays requires O(1) bitwise OR and hash set insertion per extension.
Space Complexity: O(D) (where D ≤ n(n + 1) / 2) to store unique OR values in the hash set.
Optimal Approach
The brute-force approach performs repeated work because different subarrays ending at the same position can produce the same bitwise OR value. Instead of processing every subarray separately, the optimal approach stores only the distinct bitwise OR values of subarrays ending at the previous position.
For each new element, a subarray ending at the current position can be formed in two ways:
Start a new subarray containing only the current element.
Extend an existing subarray ending at the previous position by including the current element and calculating the bitwise OR.
A new set stores all distinct OR values obtained at the current position. These values are also added to a global set that tracks every unique OR result found so far. After processing the current element, its set of distinct OR values becomes the previous set for the next iteration.
Why is this efficient?
Bitwise OR can only turn bits from 0 to 1, never from 1 to 0. As a subarray extends toward the left, each change in its OR value must turn on at least one additional bit. Therefore, for integers represented using W bits, there can be at most W + 1 distinct OR values for subarrays ending at a particular position. This keeps the number of values processed at each step small.
Algorithm
Create an empty set to store distinct bitwise OR values of subarrays ending at the previous position, and another set to store all unique OR values.
Traverse the array from left to right, processing one element at a time.
Create a new set containing the current element to represent the single-element subarray.
For every OR value stored from the previous position, calculate its bitwise OR with the current element and add the result to the new set.
Add all values from the new set to the overall results set.
Replace the previous set with the current set so the next iteration can extend subarrays ending at this position.
After processing all elements, return the number of distinct values in the overall results set.
Dry Run
Count Distinct Bitwise OR Values of Subarrays - Optimal
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the count of distinct bitwise OR values of every subarray. int subarrayBitwiseORs(vector<int>& arr) { // Main set to store all unique bitwise OR values from all subarrays unordered_set<int> result; // Stores distinct OR values of subarrays ending at the previous index unordered_set<int> prev; for (int x : arr) { // Stores distinct OR values of subarrays ending at the current index unordered_set<int> curr; // Single-element subarray [x] curr.insert(x); // Extend all previous subarrays by taking bitwise OR with current element x for (int value : prev) { curr.insert(value | x); } // Insert all new OR values formed at this index into the overall result for (int value : curr) { result.insert(value); } // Move curr to prev for the next iteration prev = curr; } return result.size(); }};// Driver codeint main() { vector<int> arr = {1, 2, 3}; Solution solution; cout << solution.subarrayBitwiseORs(arr) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(N * W) (or O(N) for fixed 32-bit integers), as at most W + 1 distinct OR values are processed at each index in O(1) expected time per insertion.
Space Complexity: O(D), where D is the total number of distinct subarray OR values. The result set stores all D values, and prev and curr each store at most D values.
Interview follow-up Questions
Bitwise OR can only turn 0-bits into 1-bits, never back to 0. As a subarray extends leftwards, its OR value can change at most W times (once for each newly set bit) plus the initial single element. This guarantees that prev never contains more than W + 1 distinct values.
Be the first to add a comment.