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