Can anyone explain their solution to the following problem -
“Given N nodes numbered 1 to N there is an undirected edge of cost 1 between nodes i and j if (i xor j) has exactly 2 set bits. Find the length of the shortest path if it exists from node a to b”
Constraints -
1<=T<=10
1<=N<=10000000
The contest is now over
I haven’t done the contest, but here’s how I would solve it with a simple implementation:
The statement "i \oplus j has exactly 2 set bits" means that node i has an edge to j if they differ by exactly 2 bits in their binary representation. So in one “move”, you can flip exactly 2 bits of a. Let’s find the number of bits in which a differs from b and call it x (one-line implementation: __builtin_popcount(a ^ b)). If x is even, you can reach b in \frac{x}{2} moves, otherwise, it’s impossible (because you always have to flip an even number of bits). Complexity: O(1) per test case.
As a bonus: you may ask, how do we avoid the constraint that the numbers have to be less than or equal to n? We use the fact that a, b \leq n. First, we switch off the bits that are set in a but not in b. Then, we have some number y \leq a, b \leq n. Now we switch on the bits that are set in b (these two steps may be combined, it makes no difference). In both of these steps, we never exceed the maximum of a and b, so the path is always achievable.
When x is odd, is it possible to reach a number k which differs from b by even number of bit positions?
Yes, but not a itself
What if the set bits constraint is set to 3 or 4 or any other general value k will our answer will be __builtin_popcount(a^b)/k?