Daily DSA: Subarray Bitwise OR Product Minimization (Hard)
Advertisement
Problem Statement
You are given an array of non-negative integers $A$ of size $N$.
For any contiguous subarray $A[l..r]$ ($0 \le l \le r < N$), define its value as the bitwise OR of all elements in the subarray multiplied by the length of the subarray. Formally, $\text{Value}(l, r) = \left( \bigvee_{i=l}^{r} A[i] \right) \times (r - l + 1)$.
Return the minimum value among all possible contiguous subarrays of $A$.
Examples
Example 1:
Input: A = [1, 3, 2]
Output: 2
Explanation:
- Subarray
[1..1]: OR = 1, length = 1, Value = $1 \times 1 = 1$. - Subarray
[2..2]: OR = 2, length = 1, Value = $2 \times 1 = 2$. - Subarray
[1..2]: OR = 3, length = 2, Value = $3 \times 2 = 6$. - Subarray
[0..1]: OR = 3, length = 2, Value = $3 \times 2 = 6$. - Subarray
[0..2]: OR = 3, length = 3, Value = $3 \times 3 = 9$. - Subarray
[0..0]: OR = 1, length = 1, Value = $1 \times 1 = 1$. Wait, let’s check[1..1]which is elements[3], length 1, value 3. Wait, index 0 is1, index 1 is3, index 2 is2. Subarrays and values: [0..0]->1 * 1 = 1[1..1]->3 * 1 = 3[2..2]->2 * 1 = 2[0..1]->(1 | 3) * 2 = 3 * 2 = 6[1..2]->(3 | 2) * 2 = 3 * 2 = 6[0..2]->(1 | 3 | 2) * 3 = 3 * 3 = 9The minimum value is1(from subarray[0..0]or similar). Wait, let’s use an example where the answer is more illustrative.
Example 2:
Input: A = [2, 1, 4]
Output: 3
Explanation:
- Subarray
[1..2]is[1, 4], OR is1 | 4 = 5, length is 2, value is $5 \times 2 = 10$. - Subarray
[1..1]is[1], OR is1, length is 1, value is $1 \times 1 = 1$. - Subarray
[0..1]is[2, 1], OR is3, length is 2, value is $3 \times 2 = 6$. - Subarray
[0..2]is[2, 1, 4], OR is7, length is 3, value is $7 \times 3 = 21$. Minimum is 1? Wait,[1]has value $1 \times 1 = 1$. Let’s adjust example 2 to make minimum 3:[3, 2, 4]. Subarray[1..1]is[2], value $2 \times 1 = 2$. Let’s provide standard clear output forA = [1, 2, 4]: - Subarray
[0..0]:1 * 1 = 1 - Subarray
[1..1]:2 * 1 = 2 - Subarray
[2..2]:4 * 1 = 4 - Subarray
[0..1]:(1 | 2) * 2 = 3 * 2 = 6 - Subarray
[1..2]:(2 | 4) * 2 = 6 * 2 = 12 - Subarray
[0..2]:(1 | 2 | 4) * 3 = 7 * 3 = 21Minimum is 1.
Constraints
- $1 \le N \le 10^5$
- $0 \le A[i] \le 10^6$
Approach
- Observation on Bitwise OR: As the length of the subarray increases, the bitwise OR sum is non-decreasing. There are at most $O(N \log(\max A))$ distinct bitwise OR values for subarrays ending at any index $r$.
- Monotonic Traversal / Stack: We can track the ranges for each bit position. For each bit $b$ from $0$ to $19$, we can find the intervals where bit $b$ is set.
- Alternatively, since the number of distinct OR values ending at index $i$ is at most $\log(\max A)$, we can maintain all distinct OR values and their corresponding left boundary ranges using a stack or vector, updating them as we append $A[i]$.
- For each ending index $r$, we iterate through the distinct OR values of subarrays ending at $r$. For an OR value $V$ spanning from index $l_{start}$ to $l_{end}$, the minimum length is achieved at $l_{end}$ (the largest starting index that yields this OR value), and the product is $V \times (r - l_{end} + 1)$.
- Time complexity will be $O(N \log(\max A))$, which easily fits within the limits.
C++ Solution
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
long long minimumSubarrayORProduct(vector<int>& A) {
int n = A.size();
long long min_val = -1;
// Stores pairs of (OR_value, left_most_index)
vector<pair<int, int>> prev_ors;
for (int i = 0; i < n; ++i) {
vector<pair<int, int>> curr_ors;
curr_ors.push_back({A[i], i});
for (auto& p : prev_ors) {
int new_or = p.first | A[i];
if (curr_ors.back().first == new_or) {
// Keep the leftmost index for the same OR value
curr_ors.back().second = min(curr_ors.back().second, p.second);
} else {
curr_ors.push_back({new_or, p.second});
}
}
prev_ors = move(curr_ors);
for (auto& p : prev_ors) {
long long val = (long long)p.first * (i - p.second + 1);
if (min_val == -1 || val < min_val) {
min_val = val;
}
}
}
return min_val;
}
};
Complexity Analysis
- Time Complexity: $O(N \log(\max A))$, because for each of the $N$ elements, the number of distinct bitwise OR values ending at index $i$ is bounded by the number of bits in $\max A$ (which is at most $\approx 20$).
- Space Complexity: $O(\log(\max A))$ auxiliary space to store the distinct OR values for the current step.
Advertisement