SUBARRAY OR

Given an array of integers A of size N.

Value of a subarray is defined as BITWISE OR of all elements in it.

Return the sum of Value of all subarrays of A % 10^9 + 7.

The first argument given is the integer array A.

Return the sum of Value of all subarrays of A % 10^9 + 7.

1 <= N <= 10^5
1 <= A[i] <= 10^8

Input 1:
    A = [1, 2, 3, 4, 5]
Output 1:
    71
Explanation 1:
    Value( [ 1 ] ) =	1
    Value( [ 1,2 ] ) =	3
    Value( [ 1,2,3 ] ) =	3
    Value( [ 1,2,3,4 ] ) =	7
    Value( [ 1,2,3,4,5 ] ) =	7
    Value( [ 2 ] ) =	2
    Value( [ 2,3 ] ) =	3
    Value( [ 2,3,4 ] ) =	7
    Value( [ 2,3,4,5 ] ) =	7
    Value( [ 3 ] ) =	3
    Value( [ 3,4 ] ) =	7
    Value( [ 3,4,5 ] ) =	7
    Value( [ 4 ] ) =	4
    Value( [ 4,5 ] ) =	5
    Value( [ 5 ] ) =	5
    Sum of all these values = 71

Input 2:
    A = [7, 8, 9, 10]
Output 2:
    110

Solution:

Time: O(n^2)
Space: O(n)

public class Solution {
    public int solve(int[] A) {
        // dp[i][j] = subarray all for elements from [i, j]
        // dp[i][i] = A[i]
        // dp[i][j] = dp[i][j - 1] | A[j]
        // sum(dp[i][j])
        int n = A.length;
        int sum = 0;
        int mod = (int) 1e9 + 7;
        int[] dp = new int[n];
        for (int i = 0; i < n; i ++) {
            for (int j = i; j < n; j ++) {
                if (i == j) {
                    dp[j] = A[i];
                } else {
                    dp[j] = dp[j - 1] | A[j];
                }
                sum = (sum + dp[j]) % mod;
            }
        }
        return sum;
    }
}

Solution 2:

Time: O(n logmax)

import java.math.BigInteger;

public class Solution {
    public int solve(int[] A) {
        int n = A.length;
        int max = A[0];
        for (int i = 1; i < n; i ++) {
            max = Math.max(max, A[i]);
        }
        int l = 0;
        while (max > 0) {
            l ++;
            max = max >> 1;
        }
        int modInt = (int) 1e9 + 7;
        BigInteger mod = new BigInteger(String.valueOf(modInt));
        int totalSubArray = (1 + n) * n / 2;
        BigInteger sum = BigInteger.ZERO;
        for (int i = 0; i < l; i ++) {
            List<Integer> zeroIndices = new ArrayList<>();
            for (int j = 0; j < n; j ++) {
                int val = A[j];
                if ( ((val >> i) & 1) == 0 ) {
                    zeroIndices.add(j);
                }
            }
            int run = 1;
            int countNotSet = 0;
            if (zeroIndices.size() > 0) {
                for (int k = 1; k < zeroIndices.size(); k ++) {
                    if (zeroIndices.get(k) - zeroIndices.get(k - 1) == 1) {
                        run ++;
                    } else {
                        countNotSet += (1 + run) * run / 2;
                        run = 1;
                    }
                }
                countNotSet += (1 + run) * run / 2;
            }
            int power = (int) (Math.pow(2, i)) % modInt;
            int count = totalSubArray - countNotSet;
            BigInteger p = new BigInteger(String.valueOf(power));
            BigInteger c = new BigInteger(String.valueOf(count));
            sum = sum.add(p.multiply(c));
            // sum = (sum + curDigitSum) % modInt;
        }
        return sum.mod(mod).intValue();
    }
}

Solution3:

public class Solution {
    public int solve(int[] A) {
        long ans = 0;
        int prev[] = new int[32];
        
        //Arrays.fill(prev,-1);no need coz we are filling this array from i which starts from 1 not 0
 
        for(int i = 1; i <= A.length; i++) {
             int temp = A[i - 1];
             for(int j = 0; j < 32; j++){
                 long pow = (1 << j);
                 if((temp & pow) != 0) {
                     ans = (ans + (pow * i) % 1000000007) % 1000000007;
                     prev[j] = i;
                 } else if(prev[j] != 0) {
                     ans = (ans + (pow * prev[j]) % 1000000007) % 1000000007;
                 }
             }
         }
      
        return (int) (ans % 1000000007);  
    }
}