The link to problem : https://www.codechef.com/problems/KMXOR
Solution
We take an example to understand the solution.
Binary representation of 9 is 1001
Because we have to make maximum XOR so it is obvious for n=1 we will print k.
Now, for n=2 what we can observe is that if we take complement of k and XOR with k we will get every bit 1 which will provide us the maximum XOR. The complement shall always be smaller than k because its leftmost bit will become 0. Hence for n=2 we can print k and its complement.
eg:- 2 9
9 6
Our motive is to make every bit of k as 1.
Consider for k=9
1111 = 1000 ⊕ 100 ⊕ 11
15 8 4 3
Consider for k=5
111 = 100 ⊕ 10 ⊕ 1
7 4 2 1
We can see that for given k XOR can be made maximum equal to next nearest power of 2 minus 1 from k as XOR of weights of bits which can never be greater than k.
For n=3, the first two numbers can be the weight of leftmost bits and because now we know that maximum XOR. hence, we can simply subtract maximum XOR with sum of first two numbers to get third number.
In above example for k=9 to get third number we did 15-8-4=3.
Hence, we found numbers for n=2 and n=3.
Now because XOR of two numbers will be 0 hence for even n we can use two numbers from n=2 case and set all other numbers to a same value less than or equal to k. Similarly, for odd n we can use three numbers from n=3 case and set all other numbers to a same value less than or equal to k.
But what if we get value of k such that it binary representation has all 1’s.
When we will find complement for even n it will be 0. Hence the two numbers will be
k-1 and 1.
eg:- 111 = 110 ⊕ 1
7 6 1
For k=2 and n=3 the above solution won’t work hence, it has to be considered separately.
Time Complexity
The time complexity of solution will be O(n)
Competitive Programming 