Can someone please help me solve this problem. I came up with the following observations:
1) the first bit of the binary number should be 1.
2) we can think of each binary prefix(modulo n) as a node of the graph. So finally we need to find a hamiltonian cycle starting at 0 and ending at 0 where each node has an outgoing edge to the nodes (2*node)%n and (2*node+1)%n.
I am unable to progress further. Any help/hint will be really helpful.
Auto comment: topic has been updated by aditya_sheth (previous revision, new revision, compare).
I don't know why, but this idea got AC: Let's solve the problem from the end. Let's say that we have variable curmod.In the beginning curmod = 0.Now, when we solve the problem for prefix 1..i we know that curmod = number[1...i] % N.If curmod % 2 == 1 then in the i-th position we must put 1, otherwise 0. How to calculate curmod for prefix 1...i-1? We know that curmod = number[1...i-1] * 2 + curmod % 2.That's why curmod for prefix 1...i-1 equals either (n + curmod — (curmod & 1)) / 2 or (curmod — (curmod & 1)) / 2. And when I explored the second testcase, I noticed that if it's possible, we have to use first option, otherwise second.
Code: https://ideone.com/6Tv9Fh