How to find SUBARRAY OR of array

Question

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 % 109 + 7.

Input A = [1, 2, 3, 4, 5]

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

Code is below

def solve(a):
        n = len(a)
        mod = 10 ** 9 + 7
        sum2 = 0;
        for i in range(n):
            sum1 = 0
            for j in range(i, n):
                sum1 = (sum1 | a[j]);
                sum2 = sum2 + sum1;
        return sum2 % mod;

I got error Time Limit Exceeded. For small array i am getting correct output

How to reduce to TIME complexity.

Logic is how much contribution each set bet ex: [5, 9, 14]

Subarays are OR of [5] = 5 (0101)

OR of [9] = 9 (1110)

OR of[14] = 14 (1001)

OR of [5,9] = 15 (0101 + 1110 = 1111)

OR of [9,14] = 15 (1111)

OR of [5,9,14] = 15 (1111)

5 setbits are 1 at 3rd bit = 5x2**3
5 setbits are 1 at 2nd bit = 5x2**2
4 setbits are 1 at 1st bit = 5x2**1
5 setbits are 1 at 0th bit = 5x2**0

5x2^3 + 5x2^2 + 4x2^1 + 5x2^0 = 71

Below code using bit wise also giving me time limit exceed error

def solve(a):
        mod = 10 ** 9 + 7
        n = len(a)
        ans = 0
        for i in range(32):
            ind = n
            for j in range(n-1, -1,-1):
                bit = bool((a[j] >> i) &1)
                if bit:
                    ind = j
                ans += (n-ind)*pow(2,i)  
    
        return ans % mod   
solve([1,2,3,4,5])

Even the above code also gave a Time limit exceed error

Answer 1

It seems you are running your code on a server which has set some limitations for execuation time, such as competitive programming contests.

This link explains the reasons why you might get the Time Limit Exceed error and how to handle it:
How to overcome Time Limit Exceed(TLE)?

---

Overcome Time Limit Errors

• Change methods of Input-Output

  • This methods are only used for C/C++ and Java programming languages, and there isn't any faster way to input or output in Python

• Bounds of loops may be reduced

  • Read the bounds in the input carefully before writing your program.
  • Figure out which inputs will cause your program to run slower.
  • If a problem tells you that N <= 100000 , and your program has nested loops each which go up to N, your program will never be fast enough.

• Optimize your Algorithm

  • If nothing works after all this, then you should try changing the algorithm or the approach you are using to solve your problem.

• Look for Suggestions given

  • Look at the comments given below, any problem in which other programmers might have given a hint on how the problem can be solved better and more efficiently hinted at
  • When you overcome TLE try more exhaustive and corner test cases against your program to check the performance.

---

I highly suggest to use C++ programming language for this type of contests.

Answer 2

Use mod in the right place

def solve(a):
        mod = 10 ** 9 + 7
        n = len(a)
        ans = 0
        for i in range(32):
            ind = n
            for j in range(n-1, -1,-1):
                bit = bool((a[j] >> i) &1)
                if bit:
                    ind = j
                ans = (ans + ((n-ind)*pow(2,i,mod)) % mod) % mod  
        return ans

Answer 3

def solve(self, A):
    n = len(A)
    ans = 0
    p2 = 1
    for i in range(30):
        ind  = n
        for j in reversed(range(n)):
            #bit = bool((A[j]>>i)&1)
            bit = bool(A[j] & p2)
            if bit:
                ind = j
            ans += (n-ind)*(p2)
        p2 *= 2
    return ans %(10**9+7)

This will not give TLE.