Search code examples
javaarraysbit-manipulation

Sum of bitwise OR of all subarrays of an array using java

You are given an array of integers A of size N.

The 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.

public class Solution {
    public int solve(ArrayList<Integer> A) {
        long M = 1000000007;

        int N = A.size();
        
        long totalSubarrays = (N*(N+1))/2;
        long totalORSum = 0; //sum of bitwise OR of all subarrays
        
        //step1: traverse through each bit of element of array
        for(int i = 0; i < 32; i++) {
            long subArrayUnsetBit = 0;
            long zeroCount = 0;
            for(int j = 0; j < N; j++) {
                //2.check if bit is unset(0).count the number of unset bits.
                //Calculate the number of sub arrays with unset ith bit position

                //for each element, check if bit at "position" is unset
                //if it's unset, add to the total
                //since we are looking for number of subarrays, if there are continuous unset bit position, the number of subarrays will depend on it as well. 
                if ((1 & (A.get(j) >> i)) != 1) {
                    zeroCount++;
                } else {
                    subArrayUnsetBit = subArrayUnsetBit + (zeroCount * (zeroCount + 1)) / 2;
                    zeroCount = 0;//reset
                }

            }
            //get the number of subarrays which have ith bit as unset
            subArrayUnsetBit = subArrayUnsetBit + (zeroCount*(zeroCount+1))/2;
            //number of sub arrays which have ith bit set
            long subArraySetBit = totalSubarrays - subArrayUnsetBit;
            //if ith bit is set, its value would be: 2^i == (1<<i)
            long powerValue = (1<<i);
            //contribution to total sum by all subarrays which has set bit at ith position
            long contribution = (subArraySetBit * powerValue);
            totalORSum = (totalORSum + contribution);

        }
        return (int)(totalORSum % M);
        
    }
}

The above code is working perfectly fine for small size arrays ex:[1,2,3,4,5] answer = 71. But failing for large test cases. enter image description here

Please help with what I'm missing?

Solution

  • By changing the array length(N) to long data type. I was able to handle hard test cases efficiently.

    int N = A.size();

    to

    long N = A.size();