Subarray Or
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.recursion;
import java.util.*;
/ * Problem: Subarray Or * Group: 07. Recursion */ / * ============================================================================================ * PROBLEM: Subarray OR * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Given an array of integers A of size N. * The value of a subarray is defined as the BITWISE OR of all elements in it. * Return the sum of values of all subarrays of A modulo (10^9 + 7). * * --------------------- * 2. Logical Breakdown & Mathematical Formulation * --------------------- * A naive solution would generate all N(N+1)/2 subarrays and compute their OR sum. * Time Complexity: O(N^2). With N = 10^5, this results in TLE (Time Limit Exceeded). * * Optimized Approach: Bitwise Contribution Technique * Instead of iterating subarrays, we iterate through each bit position (0 to 30) and * count how many subarrays have that specific bit set to 1. * * Let's consider the k-th bit. * 1. The k-th bit contributes (2^k) to the total sum for every subarray where the * bitwise OR has the k-th bit set. * 2. The bitwise OR of a subarray has the k-th bit set if at least one element * in that subarray has the k-th bit set. * 3. It is easier to count the complement: * Count subarrays where the k-th bit is NOT set (i.e., all elements have k-th bit 0). * * Algorithm: * For each bit position i from 0 to 30: * a. Find consecutive segments of elements where the i-th bit is 0. * b. If a segment has length L, it contributes L(L+1)/2 subarrays with i-th bit 0. * c. Total subarrays = N(N+1)/2. * d. Subarrays with bit i set = Total - (Sum of zero-bit subarrays). * e. Add (Count_Set * 2^i) to the final answer. * * --------------------- * 3. Constraints & Complexity Analysis * --------------------- * Constraints: * 1 <= N <= 10^5 * 1 <= A[i] <= 10^8 (Requires checking up to ~27-30 bits) * Modulo: 10^9 + 7 * * Time Complexity: * O(N * log(Max_A)) * - We iterate 30 times (for each bit). * - Inside, we iterate N times. * - Total operations ~ 30 * 10^5 = 3 * 10^6 (Well within time limits). * * Space Complexity: * O(1) - Auxiliary space (excluding input). * * --------------------- * 4. Input / Output Format * --------------------- * Input: Array A. * Output: Long/Integer representing sum modulo 10^9 + 7. * * --------------------- * 5. Examples * --------------------- * Input 1: A = [1, 2, 3, 4, 5] * Output 1: 71 * * Input 2: A = [7, 8, 9, 10] * Output 2: 110 * * Logic Example (A = [1, 2], Binary: 01, 10): * Bit 0: * - A[0] (1) has bit 0 ON. A[1] (2) has bit 0 OFF. * - Subarrays with bit 0 OFF: [2] -> Count = 1. * - Total subarrays = 3 ([1], [2], [1,2]). * - Subarrays with bit 0 ON = 3 - 1 = 2 ([1], [1,2]). * - Contribution: 2 * 2^0 = 2. * Bit 1: * - A[0] (1) has bit 1 OFF. A[1] (2) has bit 1 ON. * - Subarrays with bit 1 OFF: [1] -> Count = 1. * - Subarrays with bit 1 ON = 3 - 1 = 2 ([2], [1,2]). * - Contribution: 2 * 2^1 = 4. * Total = 2 + 4 = 6. * (Check: 1|2=3. Sum: 1 + 2 + 3 = 6). Correct. * * ============================================================================================ / public class SubarrayOr { public int solve(int[] A) { // TODO: Implement solution return 0; } }