 # CLNUMG - Editorial

Author: Subham Das
Tester: Soumik Sarkar
Editorialist: Soumik Sarkar

CAKEWALK

Binary numbers

### PROBLEM:

Find the minimum number which with N ones and M zeroes in its binary representation without leading zeroes.

### EXPLANATION:

The minimum number with N ones and M zeroes will have the form [1, M times 0, (N-1) times 1].
For N=4 and M=2 the answer is 100111.
For N=1 and M=3 the answer is 1000.
For N=5 and M=0 the answer is 11111.

This problem can be solved easily using bitwise operations. We can see that
[1, M times 0, (N-1) times 1] = [1, (N+M-1) times 0] | [(N-1) times 1]
[1, (N+M-1) times 0] can be obtained by 1 << (N+M-1).
[(N-1) times 1] can be obtained by (1 << (N-1)) - 1.
Here “|” is the bitwise OR operator and “<<” is the bitwise left-shift operator. Addition can also be used in place of bitwise OR.

Hence, the answer can be obtained by the code

ans = (1 << (N+M-1)) | ((1 << (N-1)) - 1)

Complexity of this approach is \mathcal{O}(1).

### TESTER’S SOLUTION:

Tester’s solution can be found here.