The problem for \(K=1\) is a famous one known as Gray code.

Below, we consider \(K \geq 2\). First, the answer is always impossible for an even \(K\), because all numbers will have the same parity of the popcount.

The case \(K=N\) is also obviously impossible.

The other cases are possible. We will show it by actually constructing the solution.

It is possible to take a basis in \(N\)-bit XOR consisting of values whose popcounts are \(K\). Let \(z_1,z_2,\cdots,z_N\) be one such basis.

Additionally, we find an \(N\)-bit Gray code (a permutation of the numbers where adjacent terms differ by exactly one bit) and name it \(a_0, a_1, \cdots, a_{2^N-1}\).

Here, let us define \(b_i\) as follows.

• \(b_i=z_{j_1} \oplus z_{j_2} \oplus \cdots\), where \(j_1,j_2,\cdots\) are the bit positions of \(1\)’s in \(a_i\).

Then, \(b\) will be the answer to the problem. Because the XOR of adjacent terms will be one of the elements of \(z\), it satisfies the condition of adjacent terms differing by exactly \(K\) bits. Additionally, since \(z\) is a basis, \(b\) will be a permutation of the numbers.

The time complexity of this method is \(O(N 2^N)\).

Sample submission (c++)