uttaran_das's blog

By uttaran_das, history, 3 years ago, In English

Problem Link : Optimal Xor Set

This is a problem from the recent Codechef Long Challenge. I find the question very much interesting, but can't able to think any optimized approach other than the brute force solution. It will be very helpful if you can tell me any approach or solution.

For the people who won't like to click the link or have any other problems, the question is like this.

Find K distinct numbers in the range [1,N] such that the bitwise XOR of all the numbers is maximized. Print any set of these numbers that maximize the XOR.


  • 1≤T≤10^4

  • 1≤K≤N≤10^6

  • The sum of N over all queries is at most 4⋅10^6.

  • The sum of K over all queries is at most 2⋅10^6.


The first line contains an integer T, the number of test cases. Then the test cases follow.

Each test case contains a single line of input, two integers N, K.


For each test case, output K distinct integers in any order as described in the problem.

Sample Input


10 1

9 2

8 7

Sample Output


7 8

1 2 3 4 5 6 8


  • Test Case 1: The only possible set is {10} which gives the value 10.

  • Test Case 2: The other possible set is {9,6} which gives the value 9⊕6=15=7⊕8.

  • Test Case 3: The only possible set is {1,2,3,4,5,6,8} which gives the value 1⊕2⊕3⊕4⊕5⊕6⊕8=15.


Full text and comments »

  • Vote: I like it
  • +13
  • Vote: I do not like it