Vaccination Drive

Easy

0/40

Average time to solve is 10m

Contributed by

28 upvotes

Asked in company

Problem statement

The Indian government recently launched the world's largest vaccination drive for COVID-19. Dr Ritesh has been appointed as a nodal officer for vaccinating a locality. There are ‘N’ houses numbers from 1 to ‘N’ in that locality. Dr Ritesh will visit each house one by one and vaccinate all the people in the house. He has already covered ‘K’ number of houses. Since ‘N’ is a very large number, ‘L’ bits are required to represent the number. You are supposed to help Dr Ritesh and find the maximum possible number of houses that are yet to be covered under the vaccination drive.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first input line of each test case contains two space-separated integers ‘K’ and ‘L’ as described in the problem.

Output Format :

For each test case, print the maximum possible number of houses that are yet to be covered under the vaccination drive.

The output of each test case will be printed in a separate line.

Note:

You are not required to print the expected output, it has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 50
1 <= ‘K’ <= N
1 <= ‘L’ <= 30

Where ‘T’ is the number of test cases, ‘K’, ‘N’ and ‘L’ are described in the problem statement.

Time limit: 1 sec

Sample Input 1 :

2
3 5
5 3

Sample output 1 :

29
3

Explanation of Sample output 1 :

For the first test case, since the number of bits required is 5, the maximum possible value for ‘N’ is 32. So the maximum possible number of remaining houses are 32 - 3 = 29.

For the second test case, since the number of bits required is 3, the maximum possible value for ‘N’ is 8. So the maximum possible number of remaining houses are 8 - 3 = 5.

Sample Input 2 :

2
1 1
2 3

Sample output 2 :

1
6

Hint 1

Hint 2

Can you think of using pow() function?

Approaches (2)

Approach 1

Approach 2

Naive approach

We know that a maximum of 2^L numbers can be represented using ‘L’ bits. Therefore a maximum possible value for ‘N’ will be 2^L. Hence, the maximum possible number of remaining houses will be 2^L - K.

We can use the inbuilt pow() function.

Time Complexity

O(log(L)), where ‘L’ is the number of bits needed to represent the number.

Since we are using the inbuilt pow(a, N) function which takes O(log(N)) time. So the overall time complexity will be O(log(L)).

Space Complexity

O(1)

We are not using any extra space.

(100% EXP penalty)

Vaccination Drive

Console