Abstract / Summary

Remove the last digit or subtract one repeatedly to reduce the number to zero with the fewest steps.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 58% (100k+ submissions).

Typical patterns to solve this problem:

• Bit Manipulation
• Enumeration

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution class implements a method makeTheIntegerZero that determines the minimum number of operations required to reduce num1 to zero by repeatedly subtracting num2 and optionally clearing bits using powers of two. The algorithm explores a bounded range of possible step counts, evaluates the residual value after subtracting num2 repeatedly, and checks whether the remaining bits can be cleared within the considered number of steps.

Core Loop

for steps in range(60 + 1):
    need = num1 - steps * num2
    if need < 0:
        break
    bits = need.bit_count()
    if bits <= steps and steps <= need:
        return steps

The loop iterates over candidate step counts from 0 through 60. For each steps value, it computes the residual need after applying steps subtractions of num2. If the residual becomes negative, the loop terminates early because further increments of steps would only increase the subtraction and keep need negative.

Bit Count Check

bits = need.bit_count()
if bits <= steps and steps <= need:
    return steps

The method uses Python’s built-in int.bit_count() to obtain the number of set bits in need. The condition bits <= steps ensures that there are enough operations available to clear each set bit, either by clearing one bit per step or by splitting larger powers of two into smaller ones. The additional constraint steps <= need guarantees that the number of steps does not exceed the magnitude of the residual, preventing impossible scenarios where more operations are claimed than the value can accommodate.

Early Termination

The if need < 0: break statement serves as an early-exit mechanism. As soon as the subtraction overshoots num1, the algorithm knows that any larger steps will only worsen the deficit, so it stops iterating. This prevents unnecessary iterations beyond the point where a solution could exist.

Return Value

If the loop finishes without satisfying the bit-count condition, the method returns -1, indicating that no feasible sequence of operations exists within the examined range.

Edge Cases Handled

When num1 is already zero, the first iteration (steps = 0) yields need = 0. The bit count of zero is also zero, satisfying bits <= steps and steps <= need (both evaluate to 0 <= 0). Consequently, the method returns 0, correctly handling the trivial case where no operations are required.

If num2 is larger than num1, the first subtraction already makes need negative. The early break triggers immediately, and the method proceeds to return -1, reflecting that it is impossible to reach zero using any number of steps.

The condition steps <= need also covers scenarios where need is positive but smaller than the current step count, ensuring that the algorithm does not claim a solution when the number of required operations exceeds the value that can be reduced.

Performance Optimizations

The algorithm limits the search space to at most 61 iterations, a constant bound that makes the runtime independent of the magnitude of the input integers. By using the built-in bit_count function, it leverages a highly optimized native implementation for counting set bits, avoiding manual loops or bitwise manipulations.

The early break on a negative need eliminates the need to continue scanning higher step counts once the subtraction has overshot, reducing the number of iterations in cases where num2 is relatively large compared to num1.

Overall, the combination of a fixed iteration ceiling, native bit counting, and early termination yields a solution that runs quickly even for the largest 64-bit integer inputs.

Imagine this code is like a magical robot trying to turn a big number into zero. To shrink the big number, the robot plays a game for a certain number of turns. In each turn, the robot picks a special number that is a power of two, like two, four, eight, or sixteen, and subtracts that from the total. The robot also has to subtract a fixed smaller number every single turn as well.

The code starts by guessing that the robot might take zero turns, then one turn, then two, and keeps going until it tries sixty turns. For every turn count, the code checks if there is a way to make the big number reach exactly zero. It looks at how many ones are hiding inside the binary version of the number, which is like counting the tiny glowing blocks that make up the number. If the number of these blocks is small enough to be removed in the chosen number of turns, then the robot celebrates because it found the right answer. If it tries many times and cannot find a way to make it reach zero, it simply gives up.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: constant
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster		Java		C++			Python	TS
	WalkCCC		Java		C++			Python
	leetcode.ca		Java	Rust	C++	C#	Go	Python	TS
	Progiez		Java		C++			Python
github	charles-wangkai		Java
	everthis	JS
	fsq			Rust
	JoshCrozier	JS
	varunu28		Java
	wisdompeak				C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	Rust
JoshCrozier	JavaScript
varunu28	Java
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality