Steps to Reduce a Number to Zero

Q: What is the time complexity of reducing a number to zero?

Running the process takes O(log n) time, because at least every second step halves the number: 61 steps for n = 2^31 - 1 . Counting the binary digits with built-in bit instructions is O(1) .

Q: Which number below 2^31 takes the most steps?

2^31 - 1 , which is thirty-one 1s in binary. It needs 31 subtractions and 30 halvings, 61 steps in total. No smaller number has as many digits and as many 1s at once.

BeginnerBit manipulation Math and simulation

+10

Start from a non-negative integer n and repeat one rule until it reaches 0: if the number is even, divide it by 2; if it is odd, subtract 1. Each application of the rule is one step. Return the number of steps it takes.

Function

numberOfSteps(n: integer) → integer

ninteger: the starting number
Returnsinteger: the number of steps until the number reaches 0

Constraints

0 ≤ n ≤ 2³¹ - 1

Examples

Input: n = 14
Output: 6
Explanation: The number goes 14 → 7 → 6 → 3 → 2 → 1 → 0: three halvings and three subtractions, 6 steps.

Input: n = 8
Output: 4
Explanation: 8 → 4 → 2 → 1 → 0. A power of two halves three times and needs one subtraction at the end, 4 steps.

Input: n = 123
Output: 12
Explanation: 123 is 1111011 in binary: seven digits and six 1s. The six 1s cost six subtractions and the six digits below the leading one cost six halvings, 12 steps.

Follow-up

Suppose an odd number may also go up by 1. What is the fewest number of steps to reach 0, and which choice is right for 15?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

In binary, halving drops the last digit, and subtracting 1 from an odd number turns its last 1 into a 0. So for n > 0 the answer is the number of binary digits plus the number of 1s, minus one. Running the rule directly is also fast: at most 61 steps.

Run the process

Intuition

Run the rule and count the steps. For 14 the loop visits 7, 6, 3, 2, 1 and 0: six steps.

A subtraction always makes an odd number even, so at least every second step is a halving. A number below 2^31 halves at most 30 times before it reaches 1. With one subtraction before each halving and one at the end, the loop runs at most 61 times. For n = 0 the loop never runs and the answer is 0.

Algorithm

Set steps to 0.
While n > 0: if n is even, set n to n / 2, otherwise to n-1.
Add 1 to steps each time.
Return steps.

def numberOfSteps(n):
    steps = 0
    while n > 0:
        if n % 2 == 0:
            n //= 2
        else:
            n -= 1
        steps += 1
    return steps

Count the binary digits

Intuition

Each step either drops the last binary digit or turns a final 1 into 0. 14 is 1110: halving gives 111, and subtracting from 111 gives 110. Every 1 must be cleared once, which costs one subtraction per 1. Every digit must be dropped, one halving each, except the leading one: when only 1 is left, its subtraction already gives 0. So the answer is length - 1 + ones, and for 14 that is 4 - 1 + 3 = 6.

Java, C, C++, Go, Rust and Swift have built-ins for both counts (leading zeros and set bits) that compile to single instructions on most processors. Other languages read the digits with % 2 in a loop of at most 31 rounds. Handle n = 0 first: it has no 1 bit to anchor the formula.

Algorithm

If n == 0, return 0.
Find length, the number of binary digits of n.
Find ones, the number of 1 bits.
Return length - 1 + ones.

def numberOfSteps(n):
    if n == 0:
        return 0
    # Every bit below the leading one costs a halving,
    # and every 1 bit costs a subtraction.
    return n.bit_length() - 1 + bin(n).count("1")

Pitfalls and edge cases

Forgetting n = 0 in the bit formula. length - 1 + ones gives -1, and a leading-zero count of 0 can be undefined (__builtin_clz(0) in C).
Counting a halving for the leading digit. 1 becomes 0 by a subtraction, so 8 = 1000 takes 4 - 1 + 1 = 4 steps, not 5.
Writing n = (n-1) / 2 for an odd number and counting one step. That line does two steps, so 14 comes out as 4 instead of 6.
Looping while n > 1. That stops before the last step, which turns 1 into 0.

Frequently asked questions3

What is the time complexity of reducing a number to zero?

Running the process takes O(log n) time, because at least every second step halves the number: 61 steps for n = 2^31 - 1. Counting the binary digits with built-in bit instructions is O(1).

Which number below 2^31 takes the most steps?

2^31 - 1, which is thirty-one 1s in binary. It needs 31 subtractions and 30 halvings, 61 steps in total. No smaller number has as many digits and as many 1s at once.

Why is halving the same as a right shift?

A binary number is a sum of powers of two. Dividing an even number by 2 lowers every power by one, which moves every digit one place right and drops the final 0. That is what n >> 1 does, so you can write the halving either way.

def numberOfSteps(n):
    # Write code here

Test #1

Test #2

Test #3

Argument

n = 14

Expected Output