Domain 1EasyCORE

Number of Steps to Reduce a Number to Zero

The problem requires us to reduce a given non-negative integer `num` to zero by performing specific operations. If the number is even, we divide it by 2; if it's odd, we subtract 1 from it. The goal is to determine the total number of steps required to reach zero.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Bit Manipulation

1342. Number of Steps to Reduce a Number to Zero

Model: qwen2.5-coder:14b
Topics: Bit Manipulation
FAANG asked: 1
Acceptance rate: 85.7%


Problem Breakdown

The problem requires us to reduce a given non-negative integer num to zero by performing specific operations. If the number is even, we divide it by 2; if it’s odd, we subtract 1 from it. The goal is to determine the total number of steps required to reach zero.

Inputs:

  • A non-negative integer num (0 <= num <= 10^6).

Outputs:

  • An integer representing the number of steps needed to reduce num to zero.

Implicit Constraints or Tricky Edge Cases:

  • The input can be zero, which requires zero steps.
  • The input is guaranteed to be a non-negative integer within a specific range, so we don’t need to handle negative numbers or overflow.

Intuition

A brute-force approach would involve repeatedly checking if the number is even or odd and performing the corresponding operation until the number becomes zero. This approach is straightforward but has a time complexity of O(log n) because each division by 2 reduces the number of bits needed to represent it by one.

The key insight here is that we can leverage bit manipulation to optimize the process. Specifically, we can use bitwise operations to determine if a number is even or odd and to perform the division operation efficiently.

Approach

  1. Initialize a counter steps to zero.
  2. Iterate while num is greater than zero:
    • If num is even (i.e., the least significant bit is 0), divide it by 2 using a right shift (num >>= 1).
    • If num is odd (i.e., the least significant bit is 1), subtract 1 from it.
    • Increment the steps counter after each operation.
  3. Return the steps counter once num reaches zero.

This approach uses bitwise operations, which are generally faster than arithmetic operations, making it more efficient.

Complexity Analysis

  • Time Complexity: O(log n), where n is the input number. This is because each division by 2 reduces the number of bits needed to represent the number by one.
  • Space Complexity: O(1), as we only use a constant amount of extra space for the steps counter.

Solution

def numberOfSteps(num: int) -> int:
    steps = 0
    while num > 0:
        if num % 2 == 0:
            num >>= 1  # Divide by 2 using right shift
        else:
            num -= 1   # Subtract 1 for odd numbers
        steps += 1
    return steps

Edge Cases Handled

  • Zero Input: If num is zero, the loop does not execute, and the function returns 0 immediately.
  • Small Numbers: The approach works efficiently even for small numbers like 1 or 2.
  • Large Numbers: Given the constraints (0 <= num <= 10^6), the solution handles large numbers within the specified range without performance issues.