Number of Steps to Reduce a Number in Binary Representation to One
Real-world version: Taps To Settle A Cell RegisterThe statement here is our own: the same inputs, outputs and technique.
A particle counter holds its running total in a row of cells given as the string cells, each cell either '0' or '1', highest place value first. The leading cell is always '1', so the row carries no padding, and the total may be far larger than a machine word.
An operator brings the total down to 1 with taps of a single key. Each tap does one of two things, and the operator has no choice about which:
- when the total is even, the tap shifts it down to half its value;
- when the total is odd, the tap raises it by one.
Return how many taps it takes to reach a total of 1. A row that already reads 1 needs none.
Examples
Example 1
- Input
- cells = "10011"
- Output
- 8
The row stands for 19. The taps run 19, 20, 10, 5, 6, 3, 4, 2, 1, which is eight taps in all.
Example 2
- Input
- cells = "1000"
- Output
- 3
The row stands for 8, and three taps bring it through 4 and 2 to 1.
Example 3
- Input
- cells = "1111"
- Output
- 5
The row stands for 15, and the taps run 15, 16, 8, 4, 2, 1.
Constraints
- 1 <= cells.length <= 500
- cells consists only of the characters '0' and '1'
- cells[0] == '1'
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def taps_to_settle(cells: str) -> int:public int tapsToSettle(String cells)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 14 test cases: 14 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's