SHADOW2 : Showing TLE

I have submitted my solution to Shadow2 but it is showing TLE. Please suggest better methods for approaching the problem . I have used Brute Force approach.

hi, suposse that you already have k consecutive numbers (p[i] xor p[i+1] xor p[i+2] … xor p[i+k-1]), the question is: how can you calculate xor from i+1 to i+k ( p[i+k] exists )?

xor has a special property: a xor a = 0, so xor from i+1 to i+k, is (p[i] xor p[i+1] xor p[i+2] … xor p[i+k-1]) xor p[i+k] xor p[i], since p[i] xor p[i] = 0, the result is gonna be (p[i+1] xor p[i+1] xor … p[i+1]), and that is what we want.

O(N) for every test

1 Like

Thanks. Beautifully explained.