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.
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-
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-
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.
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.