PROBLEM LINK:
Editorialist: Soumik Sarkar
DIFFICULTY:
EASY
PREREQUISITES:
Binary, Gray code
PROBLEM:
Given a number of binary inputs switches n, determine the number of switch flips required to go through all 2^n input configurations.
EXPLANATION:
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:
- In binary, x modulo 2^b is simply the lowest b bits of x.
- 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? 
EDITORIALIST’S SOLUTIONS:
Editorialist’s solution can be found here.