algoadvance

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

Problem Statement

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.

Clarifying Questions

  1. Q: Can the input number be negative? A: No, the problem explicitly states that the number is a positive integer.

  2. Q: Is there a maximum limit for the number? A: In general practice, we assume the number fits within the standard integer range (e.g., 32-bit signed integer).

  3. Q: Should we handle special cases where the number is already zero? A: Yes, though if the number is zero, the number of steps is trivially zero.

Strategy

  1. We will use a loop to repeatedly modify the number until it reaches zero.
  2. In each iteration, we check if the current number is even or odd:
    • If the number is even, divide it by 2.
    • If the number is odd, subtract 1 from it.
  3. We will maintain a counter to keep track of the number of steps taken.
  4. When the number becomes zero, the counter value will be our answer.

Pseudocode

steps = 0
while num > 0:
    if num is even:
        num = num / 2
    else:
        num = num - 1
    steps = steps + 1
return steps

Time Complexity

The time complexity of this algorithm is O(log N):

Code

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

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.numberOfSteps(14)); // Output: 6
        System.out.println(sol.numberOfSteps(8));  // Output: 4
        System.out.println(sol.numberOfSteps(123)); // Output: 12
    }
}

This code provides a clean and efficient solution to the problem, handling all edge cases specified in the problem statement.

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