algoadvance

Leetcode 1342. Number of Steps to Reduce a Number to Zero

Problem Statement

LeetCode Problem 1342: Number of Steps to Reduce a Number to Zero

Given an integer num, you need to repeatedly perform the following steps until num becomes 0:

1. If num is even, divide it by 2.
2. If num is odd, subtract 1 from it.

Return the number of steps to reduce num to zero.

Clarifying Questions

1. Input Constraints: What is the range of the input number?
   • The problem typically ensures 0 <= num <= 10^6.
2. Output: Should the result be of any specific type?
   • The function should return an integer indicating the number of steps.

Strategy

1. Start with num and initialize a counter to 0.
2. Use a loop to repeatedly apply the given rules:
   • If num is even, divide it by 2.
   • If num is odd, subtract 1 from it.
   • Increment the counter for each operation.
3. Stop the loop when num is zero.
4. Return the counter as the result.

Code

Here’s the C++ function to solve the problem:

#include <iostream>

int numberOfSteps(int num) {
    int steps = 0;
    while (num > 0) {
        if (num % 2 == 0) {
            num /= 2;
        } else {
            num -= 1;
        }
        steps++;
    }
    return steps;
}

// Example usage
int main() {
    int num = 14;
    std::cout << "Number of steps to reduce " << num << " to zero: " << numberOfSteps(num) << std::endl;
    return 0;
}

Time Complexity

• The time complexity is O(log n) where n is the value of the input number. This is because each division by 2 operation (for even numbers) effectively halves the size of num, and subtraction operations are constant time.

Space Complexity

• The space complexity is O(1), as we only use a fixed amount of extra space regardless of the input size.

This solution efficiently and correctly follows the steps to reduce the given number to zero.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?