I gave NCR codewars test conducted 5 days ago and here’s the 2nd problem of the test which I couldn’t solve.

You are given N-1 integers starting from 1, where N is a power of 2. In one operation you can pick two integers x and y from 1 to N-1 and swap the bits at corresponding position, For instance-

3 in binary representation is- 011

2 in binary representation is- 010

If you swap 1st bit then 3 will become 010(2 in decimal) and 2 will become 011(3 in decimal), Of course you can swap the bits at other positions too.

You can do this operation as many times you want. **You need to output the minimum non-zero product of N-1 integers modulo 10^9+7.**

Constraints-

2<=N<=10^9(I forget about constraints but it was definitely 10^5 or greater)

Open this only if you have worked with problem a little-

## Spoiler

After smashing my head for almost an hour during the contest I found this-

Let’s say my initial product is **P** = 1*2*3*...*(N-1)

I can always convert a number of the form 2^x (where x is an integer) into 1 at the cost of converting (2^x-1) into 2*(2^x-1)

Here’s an example-

4-> 0100

3-> 0011

by swapping 1st and 3rd bit 4 will become 1 and 3 will become 6. My new product P'=(P/(4*3))*1*6 which is less than P.

Similarly

8-> 1000

7-> 0111

by swapping 1st and 4th bit 8 will become 1 and 7 will become 14 and P will decrease.

And by doing this we will always get product decrease by some amount, So If P was the initial product then it will become (P/(4*8*16*...))*(2*2*2*...) we can see it is less than its initial value.

But I saw that we can further decrease the product, I don’t know how and that’s why I’ve asked the question. I couldn’t go ahead of this.