Uber OA-13 2023

Problem Description

Venky discovered himself in an extraordinary Uber binary cafeteria, renowned for its popularity and uniqueness. The cafeteria provides k various delightful desserts, each uniquely numbered from 0 to (k-1). The cost of the i-th dessert is (2^i) coins, following the binary pricing system. Venky's budget for tasting desserts is n coins, and he's only interested in purchasing each dessert once, as one tasting is sufficient for evaluation. Your task is to find how many different ways Venky can buy several desserts (possibly zero) for tasting.

Input Format:

• The first argument contains an integer n, representing the number of coins Venky is willing to spend.
• The second argument contains an integer k, representing the number of dishes available.

Output Format:

• An integer represents the number of different ways Venky can buy desserts within his budget.

Constraints:

• 1 <= n, k <=10^9

Sample Testcase 1:

Input:

n = 2, k = 1

Output:

2

Explanation:
Venky can either:

• Buy no desserts (()), or
• Buy dessert 1 ((1)).

Sample Testcase 2:

Input:

n = 2, k = 2

Output:

3

represents