how to count numbers of pairs in array of size n whose xor is equal than x for each value of 0<=x<=k ?
1<=n<=100000
1<=a[i]<=100000000
1<=k<=100000
If it is a question on any site , can you post the link of the question
This is question from Zs contest for placement.
Give some example
I have found a link for you
But I am thinking on an easier solution as well
Are you sure about the value of a[i] ??
Input
3 2
1 2 3
Output
0 1 1
Explanation
N=3 k=2
1^2=3
2^3=1
1^3=2
0 comes 0 times
1 comes 1 times
2 comes 1 times
Yes
Well you can do it like:
- Split the number into groups based on its largest 13 bits, cause they have to be exactly the same.
- Now in each group the numbers are limited at 2 ^ 17. If the group have less than 1000 elements, brute force it. Else, use Walsh Hamadard.
Complexity for Walsh is 2 ^ 17 * 17, and there are at most 100 groups containing more than 1000. The brute force sums up to at most 1000 * 1000 * 100 = 1e8 too.