Easy bitwise OR

Problem :- link text

My solution :- link text

It seems very easy why Im getting TLE and WA for some test cases.

Reason for WA:

Problem is you are overriding a[i] before calculating the next one a[i+1] here:


If a[n] is given, then you are to find b[n] such that b[i] = a[i]|a[i-1], and then after each round you are supposed to swap a and ‘b’. This is the correct way to brute force. But you would still hit TLE as k is large for 1 sec time limit.

Leaving it to you to come up with an optimized approach. Let me know if you are not able to optimise it.

Whats complexity of bitwise OR operator.Is it constant or depends on length of number in binary form??

I think there is no need to go upto k,bcoz at max All 32 bits(64 if long )will be set. So on safer side go upto 1000? Am I right

It is not about bits. See if you can find the pattern on what happens to the array A when k = 1, 2, 3, …? And what happens when n <= k? Think more, you are almost there.