Easy bitwise OR

general
,
1

Problem :- link text

My solution :- link text

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

2

Reason for WA:

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

for(i=1;i<n;i++)
{
   a[i]=a[i]|a[i-1];    
}

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.

3

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

4

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

5

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.