LeetCode Problem 1342

Difficulty: 🟢 Easy
Topics: Math, Bit Manipulation

Solution

LeetCode 1342, Number of Steps to Reduce a Number to Zero

Problem Understanding

The problem gives us a non-negative integer num and asks us to compute how many operations are required to reduce it all the way down to 0.

At every step, we apply one of two rules:

• If the current number is even, divide it by 2
• If the current number is odd, subtract 1

The process continues until the value becomes 0. The answer is simply the total number of operations performed.

For example, if the input is 14, the sequence becomes:

14 → 7 → 6 → 3 → 2 → 1 → 0

This takes six operations, so the output is 6.

The constraint is:

0 <= num <= 10^6

This is a relatively small range, which means even a direct simulation approach is completely feasible. Since each operation either removes one bit through division by 2 or converts an odd number into an even number through subtraction, the number decreases very quickly.

An important observation is that the number of operations is closely tied to the binary representation of the number. Every division by 2 removes a binary digit from the right side, while every subtraction handles an odd bit.

Several edge cases are important:

• num = 0, no operations are needed
• num = 1, exactly one subtraction is needed
• Powers of two such as 8 repeatedly divide cleanly
• Odd numbers such as 123 alternate between subtraction and division

The problem guarantees the input is a valid non-negative integer, so we do not need to handle invalid values or negative numbers.

Approaches

Brute Force Approach

The most straightforward solution is to simulate the process exactly as described.

We repeatedly check whether the current number is even or odd:

• If it is even, divide it by 2
• Otherwise, subtract 1

We maintain a counter that tracks how many operations have been performed. The loop stops once the number reaches 0.

This approach is correct because it directly follows the problem statement step by step. Every operation performed matches the required rules exactly.

Although this is called a brute-force simulation, it is actually efficient enough because the number shrinks rapidly. Each division by 2 cuts the value in half, so the total number of operations is proportional to the number of bits in the number.

Optimal Approach

The optimal approach uses the same simulation idea but recognizes an important bit manipulation insight.

A number is:

• Even if its least significant bit is 0
• Odd if its least significant bit is 1

Instead of using modulo operations, we can use bitwise operations:

• num & 1 checks parity
• num >>= 1 divides by 2

This works because shifting a binary number right by one position removes the least significant bit, which is equivalent to integer division by 2.

The algorithm remains conceptually identical, but bit operations are very natural for this problem because the operations directly correspond to binary behavior.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(log n)	O(1)	Simulates subtraction and division operations directly
Optimal	O(log n)	O(1)	Uses bit manipulation for parity checks and division

Algorithm Walkthrough

1. Initialize a variable steps to 0.

This variable will count how many operations are performed before the number becomes 0. 2. Continue looping while num > 0.

As long as the number is not zero, we still need more operations. 3. Check whether the number is even or odd.

We can determine this using:

num & 1

If the result is 0, the number is even. Otherwise, it is odd. 4. If the number is even, divide it by 2.

Using bit manipulation:

num >>= 1

This shifts all bits one position to the right, which is equivalent to integer division by 2. 5. If the number is odd, subtract 1.

This converts the odd number into an even number, allowing future division operations. 6. Increment steps after every operation.

Every subtraction or division counts as exactly one step. 7. When the loop ends, return steps.

At this point, the number has become 0, so the total count is the answer.

Why it works

The algorithm is correct because every iteration performs exactly the operation required by the problem statement. If the number is even, dividing by 2 is mandatory. If the number is odd, subtracting 1 is mandatory. Since each operation strictly decreases the number, the process must eventually terminate at 0. The counter accurately records every operation performed, so the final result is correct.

Python Solution

class Solution:
    def numberOfSteps(self, num: int) -> int:
        steps = 0

        while num > 0:
            if num & 1:
                num -= 1
            else:
                num >>= 1

            steps += 1

        return steps

The implementation begins by initializing a steps counter to track the number of operations.

The while loop continues until the number becomes 0. Inside the loop, we determine whether the number is odd using the bitwise expression num & 1.

If the number is odd, we subtract 1. Otherwise, we divide by 2 using a right shift operation.

After each operation, the step counter increases by one.

Finally, once the loop terminates, the function returns the total number of steps required to reduce the number to zero.

Go Solution

func numberOfSteps(num int) int {
    steps := 0

    for num > 0 {
        if num&1 == 1 {
            num--
        } else {
            num >>= 1
        }

        steps++
    }

    return steps
}

The Go implementation follows exactly the same logic as the Python version.

Go uses the same bitwise operators for parity checking and right shifting. Since the input constraint is very small, integer overflow is not a concern. No additional memory structures are required, so the implementation remains compact and efficient.

Worked Examples

Example 1

Input:

num = 14

Step	Current num	Operation	Result	steps
1	14	divide by 2	7	1
2	7	subtract 1	6	2
3	6	divide by 2	3	3
4	3	subtract 1	2	4
5	2	divide by 2	1	5
6	1	subtract 1	0	6

Final answer:

6

Example 2

Input:

num = 8

Step	Current num	Operation	Result	steps
1	8	divide by 2	4	1
2	4	divide by 2	2	2
3	2	divide by 2	1	3
4	1	subtract 1	0	4

Final answer:

4

Example 3

Input:

num = 123

Step	Current num	Operation	Result	steps
1	123	subtract 1	122	1
2	122	divide by 2	61	2
3	61	subtract 1	60	3
4	60	divide by 2	30	4
5	30	divide by 2	15	5
6	15	subtract 1	14	6
7	14	divide by 2	7	7
8	7	subtract 1	6	8
9	6	divide by 2	3	9
10	3	subtract 1	2	10
11	2	divide by 2	1	11
12	1	subtract 1	0	12

Final answer:

12

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	Each operation significantly reduces the number
Space	O(1)	Only a few variables are used

The time complexity is logarithmic because division by 2 removes one binary digit at a time. Even though subtraction operations occur for odd numbers, the total number of operations remains proportional to the number of bits in the integer.

The space complexity is constant because the algorithm only stores a few integer variables regardless of input size.

Test Cases

solution = Solution()

assert solution.numberOfSteps(14) == 6   # Example case
assert solution.numberOfSteps(8) == 4    # Power of two
assert solution.numberOfSteps(123) == 12 # Mixed odd and even operations

assert solution.numberOfSteps(0) == 0    # Boundary case, already zero
assert solution.numberOfSteps(1) == 1    # Single subtraction
assert solution.numberOfSteps(2) == 2    # Divide once, subtract once
assert solution.numberOfSteps(3) == 3    # Odd then even transitions
assert solution.numberOfSteps(4) == 3    # Multiple divisions

assert solution.numberOfSteps(15) == 7   # Consecutive odd reductions
assert solution.numberOfSteps(16) == 5   # Exact power of two
assert solution.numberOfSteps(1024) == 11 # Large power of two

assert solution.numberOfSteps(999999) > 0 # Large input stress test

Test	Why
14	Validates the main example
8	Tests repeated divisions
123	Tests alternating odd and even behavior
0	Verifies immediate termination
1	Smallest non-zero input
2	Simple even transition
3	Odd to even conversion
4	Multiple divide operations
15	Many odd reductions
16	Power of two behavior
1024	Large clean division chain
999999	Stress test for larger values

Edge Cases

One important edge case is num = 0. A careless implementation might enter the loop unnecessarily or return an incorrect positive value. In this implementation, the loop condition is while num > 0, so the function immediately returns 0 without performing any operations.

Another important case is when the input is a power of two, such as 8 or 1024. These numbers repeatedly divide cleanly by 2 until reaching 1, followed by one final subtraction. The implementation handles this naturally through repeated right shifts.

A third important case involves odd numbers, especially sequences of odd values such as 15. Odd numbers cannot be divided directly by 2, so subtracting 1 first is essential. A buggy implementation might attempt division immediately or mishandle parity checks. Using num & 1 guarantees that odd numbers are identified correctly before subtraction occurs.