Steps to Reduce a Number to Zero
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
- ninteger
- the starting number
- Returnsinteger
- the number of steps until the number reaches 0
Constraints
0 ≤ n ≤ 231 - 1
Examples
- Input
- n = 14
- Output
- 6
- Explanation
- The number goes
14 → 7 → 6 → 3 → 2 → 1 → 0: three halvings and three subtractions,6steps.
- 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,4steps.
- Input
- n = 123
- Output
- 12
- Explanation
123is1111011in binary: seven digits and six 1s. The six 1s cost six subtractions and the six digits below the leading one cost six halvings,12steps.
+12 hidden tests on Submit
Follow-up
Suppose an odd number may also go up by 1 instead of down. 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.
Run the rule by hand on
14and count. How many times can a 32-bit number be halved?Write the numbers in binary. What does halving do to the digits, and what does subtracting
1from an odd number do?Each 1 bit costs one subtraction, and each binary digit except the leading one costs one halving. Treat
n == 0on its own.
Solution
Running the rule is already fast: every halving cuts the number in half, so even 2^31 - 1 needs only 61 steps. The interesting part is seeing what the rule does to the binary digits. Halving drops the last digit, and subtracting 1 from an odd number turns its last 1 into a 0. So the answer is the number of digits plus the number of 1s, minus one.
Run the process
Intuition
Do what the statement says. While n is above 0, halve it if it is even, subtract 1 if it is odd, and count the step. For 14 the loop visits 7, 6, 3, 2, 1 and 0, six steps.
The loop is short because 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, and with one subtraction before each halving and one at the end, the loop runs at most 61 times.
The input 0 needs no special case: the loop condition fails at once and the answer is 0.
Algorithm
- Set
stepsto0. - While
n > 0: ifnis even, setnton / 2, otherwise ton-1. - Add
1tostepseach time. - Return
steps.
def numberOfSteps(n):
steps = 0
while n > 0:
if n % 2 == 0:
n //= 2
else:
n -= 1
steps += 1
return stepsCount the binary digits
Intuition
Watch the process in binary. 14 is 1110. Halving drops the last digit: 111. Subtracting 1 from an odd number clears its last digit, a 1: 110. So each step either removes the last digit or turns a final 1 into a 0.
Now count. Every 1 in the number must be cleared once, which costs one subtraction per 1. Every digit must be removed, which costs one halving per digit, except the leading one: when only 1 is left, the subtraction that clears it already gives 0. So the answer is length - 1 + ones. For 14 = 1110 that is 4 - 1 + 3 = 6.
Java, C, C++, Go, Rust and Swift have built-in functions for both counts (a leading-zero count and a population count) that compile to single instructions on most processors. The other languages write n in binary and count the characters, or read the digits with % 2; that is a loop of at most 31 rounds. Return 0 for n = 0 first: it has no 1 bit to anchor the formula.
Algorithm
- If
n == 0, return0. - Find
length, the number of binary digits ofn. - 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
The rule is two lines. The mistakes are in the edges and in the formula's off-by-one.
- Forgetting
n = 0in the bit formula. With no digits and no 1s,length - 1 + onesgives-1, and a leading-zero count of0may be undefined (__builtin_clz(0)in C). - Counting a halving for the leading digit.
1becomes0by a subtraction, so8 = 1000takes4 - 1 + 1 = 4steps, not5. - Merging two steps into one. Writing
n = (n-1) / 2for an odd number does a subtraction and a halving at once, so it must add2to the count, not1. Otherwise14comes out as4instead of6. - Looping while
n > 1. That stops one step early, because the last step turns1into0. The loop must run untilnis0.
Frequently asked questions4
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. For n = 2^31 - 1 that is 61 steps. Counting the binary digits with built-in bit instructions is O(1).
What is the formula for the number of steps?
For n > 0, the answer is the length of n in binary, minus one, plus the number of 1 bits. Each 1 bit costs one subtraction and each digit below the leading one costs one halving. For n = 0 the answer is 0.
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 to the right and drops the final 0. That is exactly what n >> 1 does, so you can write the halving either way.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
Python
def numberOfSteps(n):
# Write code hereCase 1
Case 2
Case 3
Input
n = 14
Expected
6