We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Steps to Reduce a Number to Zero

Number: 1444

Difficulty: Easy

Paid? No

Companies: Google, Microsoft, Hudson River Trading

Problem Description

Given an integer num, return the number of steps required to reduce it to zero. In each step, if the number is even, divide it by 2; if the number is odd, subtract 1.

Key Insights

  • If the number is even, dividing by 2 quickly reduces its size.
  • If the number is odd, subtracting 1 makes it even, allowing the next division operation.
  • The process repeats until the number becomes zero.
  • The problem can be implemented using iterative or recursive approaches with a simple loop.

Space and Time Complexity

Time Complexity: O(log n)
Space Complexity: O(1)

Solution

We use a loop that repeatedly checks if the current number is even or odd.

  • If it is even, we divide by 2, utilizing the property of binary numbers where division by 2 is equivalent to a bit right shift.
  • If it is odd, we subtract 1 to make it even.

The primary data structure is a simple integer counter to track the number of steps. The algorithm directly manipulates the integer with arithmetic operations without requiring any additional data structures.

Code Solutions

# Python solution for reducing a number to zero with detailed comments

def numberOfSteps(num: int) -> int:
    # Initialize the counter for number of steps
    steps = 0
    # Loop until the number is reduced to zero
    while num > 0:
        # Check if num is even
        if num % 2 == 0:
            # Divide by 2 if even
            num //= 2
        else:
            # Subtract 1 if odd
            num -= 1
        # Increment the step counter after each operation
        steps += 1
    # Return the total count of steps required
    return steps

# Example usage:
print(numberOfSteps(14))
← Back to All Questions