KOL16H - Editorial



Editorialist: Soumik Sarkar




Binary, Gray code


Given a number of binary inputs switches n, determine the number of switch flips required to go through all 2^n input configurations.


It is always possible to enumerate all 2^n input configurations with just 1 flip between two consecutive configurations. Such a sequence is called unit distance code for obvious reasons, otherwise known as the Gray code. Hence by following the Gray code, it is possible to go through all configurations with 2^n-1 moves, and clearly it is impossible to do better than that.

However n can be at most 10^{20}, so calculating 2^n-1 is not a good idea. The way out lies in the fact that the problem asks for the answer modulo 2^{33}. We need to use two observations about binary numbers:

  1. In binary, x modulo 2^b is simply the lowest b bits of x.
  2. In binary, 2^b-1 contains only the bit 1 repeated b times.

So, if n > 33, the answer will be 1 repeated >33 times in binary. And that number modulo 2^{33} will be just the lowest 33 bits, which are all 1! This is nothing but the number 2^{33}-1.
Concluding, if n < 33 the answer is 2^n-1, and otherwise the answer is 2^{33}-1.

Complexity is \mathcal{O}(1).
PS: The time limit is set to 2 sec, perhaps to confuse people? :stuck_out_tongue:


Editorialist’s solution can be found here.