Along a river, signal beacons are numbered 1, 2, 3, ... without limit. Each beacon's number is written in binary, and the maintenance crew only ever inspects specific bit positions on every beacon: position x, position 2x, position 3x, and so on, counting positions from the least significant bit as position 1. In other words, position i (for a positive integer i) is inspected only when i is a multiple of x. Whenever an inspected position holds a 1 in a beacon's binary number, that costs 1 unit of maintenance effort for that beacon; a beacon's total cost is the number of its inspected positions that are lit.
The crew inspects beacons in order, starting at beacon 1 and continuing upward through consecutive beacons, and the annual maintenance budget allows a total of at most k units of effort summed across every beacon inspected so far. Determine the highest-numbered beacon reachable under this budget — that is, the largest integer num such that the combined maintenance cost of beacons 1 through num does not exceed k.
A single line with two integers k and x.
A single integer: the largest num such that the total maintenance cost of beacons 1 through num is at most k.
Example 1
Input
12 1
Expected
7
Explanation
With x=1, every bit position is inspected, so a beacon's cost equals its popcount. Cumulative cost through beacon 7 is 1+1+2+1+2+2+3 = 12, which fits the budget of 12. Beacon 8 would push the cumulative cost to 13, exceeding the budget, so the answer is 7.
Example 2
Input
15 2
Expected
14
Explanation
With x=2, only positions 2, 4, 6, ... (0-indexed bits 1, 3, 5, ...) are inspected. Working through beacons 1..14, the cumulative inspected-bit cost reaches 14 (within the budget of 15), but adding beacon 15 (binary 1111, which lights both inspected positions 2 and 4) would push the cumulative cost to 16, exceeding the budget. So the answer is 14.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →