TLE in XOREngine March Challenge 2020

general
,
1

Hey all!
I am getting TLE in XOREngine problem, asked in March Long challenge 20.
My code is here CodeChef: Practical coding for everyone
Can someone help me, please ?

2

You are XORing p with all the elements of A[i]. XOR might look like a O(1) but it actually has to check all the bits and then it provides you with the XOR.

Use these property: TLE in ENGXOR - #3 by hackinet

Furthermore, you just need to iterate over arr[i] only 1 time. Count how many numbers have even bits or odd bits.

Take input p. Check if p has even bits or odd bits. You have your answer.

1 Like
3

try this way , initiate a new array of size 10^8 and store the number of bits for each number from 1 to 10^8 , now get the number of bits you want for any number while iterating over the given array .

4

Thanks a lot bro

5

You can run a loop from 0 to 255 and create a lookup table. It will give you bits for any number.

No need to iterate over 10^8.

1 Like
6

@hackinet , oh this is new to me now , thanks for posting that :yum:

1 Like
7

solution if you just want to count the number of 1s in a binary representation of a number __builtin_popcount() is a good function to use as well. Reference here if you want to learn more Errichto’s Blog

1 Like
8

yeah I used the same approach , thanks for the blog…