Maximum Number That Sum of the Prices Is Less Than or Equal to K
You are given an integer k and an integer x.
The price of a number num is calculated by counting the set bits at positions x, 2x, 3x, and so on in its binary representation, starting from the least significant bit.
The accumulated price of num is the total price of all numbers from 1 to num. A number num is considered cheap if its accumulated price is less than or equal to k.
Return the greatest cheap number.
Example 1
Input
k = 9, x = 1Output
6The accumulated price reaches 9 at 6, while 7 has accumulated price 12, so 6 is the greatest cheap number.
Example 2
Input
k = 7, x = 2Output
9The accumulated price is 6 at 9, while 10 has accumulated price 8, so 9 is the greatest cheap number.
Constraints
- 1 <= k <= 10^15
- 1 <= x <= 8