PROBLEM LINK:
Author: Subham Das
Tester: Soumik Sarkar
Editorialist: Soumik Sarkar
DIFFICULTY:
CAKEWALK
PREREQUISITES:
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.