Bit Tax Within Budget

Medium

Number the bits of a binary representation from right to left, starting at 1. The tax of a number num is the count of set bits at positions step, 2·step, 3·step, … For example, 13 = 1101: with step = 1 its tax is 3, with step = 2 it is 1 (only position 4 is set). The running tax of num is the sum of the taxes of all numbers from 1 to num. Return the largest num whose running tax does not exceed budget.

Example 1

budget=6, step=1 → 4

With step = 1 the tax is the number of ones: 1, 1, 2, 1 for 1–4, totalling 5. Number 5 has a tax of 2, which would push the total to 7 > 6.

Example 2

budget=3, step=2 → 6

Only bit 2 (weight 2) is taxed. The taxes of 1–7 are 0, 1, 1, 0, 0, 1, 1, so the total through 6 is 3, and including 7 it is 4.

Constraints

1 ≤ budget ≤ 10¹⁵
1 ≤ step ≤ 8

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Binary Search Dynamic Programming

Similar problems

Two Equal Teams With Close Totals Hard AND Pieces With Cheap Tails Hard Spot the Extra Copy Medium Longest Rising Selection Medium Nine-Dot Lock Patterns Medium

Input

budget=6, step=1

Expected

Run checks the first 3 tests in your browser. Submit checks all 128 tests on the server, hidden ones included.