Number Of Steps To Reduce A Number To Zero - Leetcode Solution

The problem "Number Of Steps To Reduce A Number To Zero" on LeetCode asks us to determine the minimum number of steps required to reduce a non-negative integer to zero. The steps are as follows:

• If the number is even, divide it by two.
• If the number is odd, subtract 1 from it.

We can solve this problem by using a simple iterative approach. We start with the given non-negative integer and keep applying the above steps until we reduce it to zero. We keep count of the number of steps that we take to reach zero.

Here's the complete solution in Python:

def numberOfSteps (num: int) -> int:
    steps = 0
    while num > 0:
        if num % 2 == 0:
            num = num // 2
        else:
            num -= 1
        steps += 1
    return steps

In the code above, we initialize a variable steps to 0, which will keep track of the number of steps we take. We then run a loop while the given non-negative integer num is greater than 0. Inside the loop, we check if num is even or odd using the modulus operator %. If it's even, we divide it by 2 using integer division //. Otherwise, we subtract 1 from it. We increment the steps counter after every operation.

Once the loop ends, we return the final value of steps, which will be the minimum number of steps required to reduce the given non-negative integer to zero.

Let's test our solution with a few examples:

assert numberOfSteps(14) == 6  # 14 -> 7 -> 6 -> 3 -> 2 -> 1 -> 0
assert numberOfSteps(8) == 4   # 8 -> 4 -> 2 -> 1 -> 0
assert numberOfSteps(123) == 12 # 123 -> 122 -> 61 -> 60 -> 30 -> 15 -> 14 -> 7 -> 6 -> 3 -> 2 -> 1 -> 0

Our solution passes all the test cases and runs in O(log N) time complexity, where N is the given non-negative integer.

1