Leetcode 898: Bitwise ORs of Subarrays
Given an array of integers, return the number of distinct bitwise OR results from all the non-empty subarrays. A subarray is a contiguous sequence of elements from the array, and the bitwise OR of a subarray is the bitwise OR of each of the integers in that subarray.
Problem
Approach
Steps
Complexity
Input: You are given an array of integers. Your task is to find the number of distinct bitwise OR results from all non-empty subarrays.
Example: Input: arr = [2, 4, 8]
Constraints:
• 1 <= arr.length <= 50000
• 0 <= arr[i] <= 10^9
Output: The output is an integer representing the number of distinct bitwise OR results from all non-empty subarrays.
Example: Output: 6
Constraints:
• The result should be an integer.
Goal: The goal is to count the number of distinct bitwise OR results from all the subarrays of the given array.
Steps:
• 1. Use two sets: one to track the current bitwise OR results for each subarray, and another to store the final distinct results.
• 2. For each element in the array, calculate the bitwise OR with each element from the previous subarrays and update the results.
• 3. Add the new results to the set of distinct results.
• 4. After processing the entire array, return the size of the distinct results set.
Goal: The problem requires counting distinct results of bitwise OR operations on subarrays within the given array length and element range.
Steps:
• The length of arr is between 1 and 50000.
• Each element of arr is between 0 and 10^9.
Assumptions:
• The input array will contain at least one element.
• The elements can be large integers, up to 10^9.
• Input: Input: arr = [2, 4, 8]
• Explanation: The distinct bitwise OR results from all subarrays are: 2, 4, 8, 6 (2 | 4), 12 (4 | 8), and 14 (2 | 4 | 8). The result is 6 distinct values.
• Input: Input: arr = [0]
• Explanation: The only subarray is [0], and the result is 0. So the output is 1.
• Input: Input: arr = [1, 1, 2]
• Explanation: The subarrays and their results are: [1], [1], [2], [1, 1], [1, 2], [1, 1, 2]. These give the OR results: 1, 1, 2, 1, 3, 3. There are 3 distinct results.
Approach: The approach involves iterating through the array and computing the bitwise OR for all possible subarrays. Using sets helps to track distinct results efficiently.
Observations:
• The bitwise OR of each subarray must be calculated and stored to ensure distinct results.
• Using a set will help in eliminating duplicates while keeping track of the results.
• The challenge is to efficiently compute the OR results for all subarrays without exceeding the time limits for large arrays.
Steps:
• 1. Initialize two sets, res and cur, to store the distinct OR results and the current OR results for each subarray.
• 2. For each element in the array, compute the OR with each element from the previous subarrays, update the current results, and add them to the set of distinct results.
• 3. At the end, return the size of the result set as the number of distinct OR results.
Empty Inputs:
• An empty input array is not allowed based on the problem constraints.
Large Inputs:
• For large arrays, the solution must efficiently compute the OR results without exceeding time limits.
Special Values:
• Arrays with all elements as zero should still count as one distinct OR result (0).
Constraints:
• The solution must be optimized to handle arrays with up to 50,000 elements.
int subarrayBitwiseORs(vector<int>& arr) {
unordered_set<int> res, cur, cur2;
for(int x : arr) {
cur2 = { x };
for(int i : cur) cur2.insert(i | x);
for(int j : cur = cur2) res.insert(j);
}
return res.size();
}
1 : Function Declaration
int subarrayBitwiseORs(vector<int>& arr) {
The function `subarrayBitwiseORs` is defined, which takes a reference to a vector `arr` and returns an integer, representing the number of distinct bitwise OR results from all subarrays.
2 : Variable Initialization
unordered_set<int> res, cur, cur2;
Three unordered sets are initialized: `res` will store the final distinct results, `cur` keeps track of the OR values of the current subarray, and `cur2` is used temporarily to hold new OR results during iteration.
3 :
4 : Main Loop
for(int x : arr) {
The loop iterates through each element `x` of the array `arr`.
5 : Set Initialization
cur2 = { x };
The set `cur2` is initialized with the current element `x`, starting a new subarray OR operation.
6 : Bitwise OR Update
for(int i : cur) cur2.insert(i | x);
For each element `i` in the `cur` set, the bitwise OR operation between `i` and the current element `x` is computed, and the result is inserted into `cur2`.
7 : Update Final Set
for(int j : cur = cur2) res.insert(j);
After updating `cur2`, the set `cur` is set to `cur2`, and the distinct results from `cur2` are inserted into the result set `res`.
8 : End of Loop
}
The loop ends here, and the next element in the array will be processed.
9 :
10 : Return Statement
return res.size();
The function returns the size of the set `res`, which represents the number of distinct bitwise OR results from all subarrays.
11 : Function End
}
The function ends here.
Best Case: O(n)
Average Case: O(n^2)
Worst Case: O(n^2)
Description: The time complexity is O(n^2) in the worst case due to processing each element in all possible subarrays.
Best Case: O(1)
Worst Case: O(n)
Description: The space complexity is O(n) due to the use of sets to track the distinct OR results for subarrays.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus