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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Steps to Reduce a Number to Zero

Difficulty: Easy

Problem Description

Given an integer num, return the number of steps to reduce it to zero. In one step, if the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.

Key Insights

  • If the number is even, dividing by 2 reduces its size significantly.
  • If the number is odd, subtracting 1 makes it even, allowing for division in the next step.
  • The process continues until the number reaches zero, and each operation counts as a step.

Space and Time Complexity

Time Complexity: O(log n) due to the halving of the number when it's even.
Space Complexity: O(1) as we are using a constant amount of space.

Solution

The algorithm follows a simple loop where it checks if the number is even or odd. If it's even, we divide it by 2; if it's odd, we subtract 1. We repeat this process until the number reaches zero, incrementing a step counter for each operation. This approach efficiently reduces the number using basic arithmetic operations.

Code Solutions

def numberOfSteps(num: int) -> int:
    steps = 0
    while num > 0:
        if num % 2 == 0:
            num //= 2  # If even, divide by 2
        else:
            num -= 1   # If odd, subtract 1
        steps += 1
    return steps
← Back to All Questions