Number of Steps to Reduce a Number to Zero solution and explanation
Google
9 more videos on this problem
Number of Steps to Reduce a Number to Zero | Live Coding with Explanation | Leetcode - 1342Algorithms Made Easy · 3:42 · 3K views
Number of Steps to Reduce a Number to Zero | Leetcode 1342Coding Decoded · 5:10 · 1K views
1342. Number of Steps to Reduce a Number to Zero | Interview Preparation | English | code iocode io - English · 7:22 · 854 views
Leetcode 1342. Number of Steps to Reduce a Number to Zero PythonTechZoo · 2:17 · 684 views
Number of Steps to Reduce a Number to Zero | Leetcode 1342 | Live coding sessionCoding Decoded · 2:46 · 432 views
Leetcode Solution - 1342 Number of Steps to Reduce a Number to ZeroJohn Leonardo · 3:36 · 331 views
leetcode - 1342 Number of Steps to Reduce a Number to Zero JavaScript SolutionlitCode · 6:18 · 331 views
LEETCODE SOLUTION 1342 | Number of Steps to Reduce a Number to Zero | LEETCODE CONTEST | EASY |CodingForBeginners · 4:59 · 258 views
Leetcode Number of Steps to Reduce a Number to Zero in JavaScriptKnowledge Mavens · 4:38 · 188 views
Number of Steps to Reduce a Number to Zero - LeetCode 1342Last Programmer · 9:19 · 150 views
The problem
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.
Example 1:
Input: num = 14 Output: 6 Explanation: Step 1) 14 is even; divide by 2 and obtain 7. Step 2) 7 is odd; subtract 1 and obtain 6. Step 3) 6 is even; divide by 2 and obtain 3. Step 4) 3 is odd; subtract 1 and obtain 2. Step 5) 2 is even; divide by 2 and obtain 1. Step 6) 1 is odd; subtract 1 and obtain 0.
Example 2:
Input: num = 8 Output: 4 Explanation: Step 1) 8 is even; divide by 2 and obtain 4. Step 2) 4 is even; divide by 2 and obtain 2. Step 3) 2 is even; divide by 2 and obtain 1. Step 4) 1 is odd; subtract 1 and obtain 0.
Example 3:
Input: num = 123 Output: 12
Constraints:
0 <= num <= 106
Approach overview
Problem Overview: You are given an integer num. If the number is even, divide it by 2. If it is odd, subtract 1. Repeat until the value becomes 0 and return the total number of operations performed.
Approach 1: Iterative Simulation (O(log n) time, O(1) space)
The most direct approach simulates the operations exactly as described. Start with num and repeatedly apply the rule: if num % 2 == 0, divide by 2; otherwise subtract 1. Each operation reduces the magnitude of the number quickly, especially the division by 2 which removes one binary digit. Because each step either clears the least significant bit or shifts the number right, the loop runs proportional to the number of bits in num, giving O(log n) time. This approach uses constant extra memory and works well in any language.
The key insight comes from bit manipulation. In binary, subtracting 1 removes a trailing 1, and dividing by 2 shifts bits right. That means every 1 bit contributes one subtraction step, while every bit position contributes one division step except the last. This explains why the algorithm runs in logarithmic time relative to the value of num.
Approach 2: Recursive Reduction (O(log n) time, O(log n) space)
The same logic can be expressed recursively. Define a function that returns 0 when num == 0. For other values, perform one operation and call the function on the updated number. If the number is even, recurse with num / 2; otherwise recurse with num - 1. Each recursive call reduces the number toward zero, so the recursion depth equals the number of operations performed.
This version highlights the mathematical structure of the problem and maps naturally to the rules described in the prompt. However, it uses call stack space proportional to the number of steps, which is O(log n). In practice, the iterative version is usually preferred for production code because it avoids recursion overhead.
The problem primarily falls under math reasoning and bit manipulation, since the operations correspond directly to binary properties of the number.
Recommended for interviews: The iterative approach. It is simple, efficient, and demonstrates clear reasoning about how repeated division shrinks the number. Explaining the binary interpretation (each bit causing either a subtract or divide step) shows deeper understanding and often impresses interviewers.
Approach 1: Iterative Approach
In this approach, we use a loop to repetitively apply the given conditions on the number. If the number is even, divide it by 2, and if odd, subtract 1. We count and return the number of operations needed to reduce the number to zero.
def numberOfSteps(num):
steps = 0
while num > 0:
if num % 2 == 0:
num //= 2
else:
num -= 1
steps += 1
return steps
num = 14
print("Number of steps:", numberOfSteps(num))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 solution = new Solution();
int num = 14;
System.out.println("Number of steps: " + solution.numberOfSteps(num));
}
}#include <iostream>
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;
}
};
int main() {
Solution s;
int num = 14;
std::cout << "Number of steps: " << s.numberOfSteps(num) << std::endl;
return 0;
}function numberOfSteps(num) {
let steps = 0;
while (num > 0) {
if (num % 2 === 0) {
num /= 2;
} else {
num -= 1;
}
steps++;
}
return steps;
}
let num = 14;
console.log('Number of steps:', numberOfSteps(num));#include <stdio.h>
int numberOfSteps(int num) {
int steps = 0;
while (num > 0) {
if (num % 2 == 0) {
num /= 2;
} else {
num -= 1;
}
steps++;
}
return steps;
}
int main() {
int num = 14;
printf("Number of steps: %d", numberOfSteps(num));
return 0;
}using System;
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;
}
static void Main() {
Solution s = new Solution();
int num = 14;
Console.WriteLine("Number of steps: " + s.NumberOfSteps(num));
}
}A straightforward iterative solution in Python using a while loop to repetitively perform the operations until the number becomes zero.
Time Complexity: O(log n)
Space Complexity: O(1)
Approach 2: Recursive Approach
This approach uses recursion to handle the problem. The function calls itself with the same logical conditions: divide by 2 for even or subtract 1 for odd, until the base case of zero is reached. It accumulates the count of steps through recursive calls.
def numberOfSteps(num):
if num == 0:
return 0
return 1 + numberOfSteps(num // 2 if num % 2 == 0 else num - 1)
num = 14
print("Number of steps:", numberOfSteps(num))public class Solution {
public int numberOfSteps(int num) {
if (num == 0) return 0;
return 1 + numberOfSteps(num % 2 == 0 ? num / 2 : num - 1);
}
public static void main(String[] args) {
Solution solution = new Solution();
int num = 14;
System.out.println("Number of steps: " + solution.numberOfSteps(num));
}
}#include <iostream>
class Solution {
public:
int numberOfSteps(int num) {
if (num == 0) return 0;
return 1 + numberOfSteps(num % 2 == 0 ? num / 2 : num - 1);
}
};
int main() {
Solution s;
int num = 14;
std::cout << "Number of steps: " << s.numberOfSteps(num) << std::endl;
return 0;
}function numberOfSteps(num) {
if (num === 0) return 0;
return 1 + numberOfSteps(num % 2 === 0 ? num / 2 : num - 1);
}
let num = 14;
console.log('Number of steps:', numberOfSteps(num));#include <stdio.h>
int numberOfSteps(int num) {
if (num == 0) return 0;
return 1 + numberOfSteps(num % 2 == 0 ? num / 2 : num - 1);
}
int main() {
int num = 14;
printf("Number of steps: %d", numberOfSteps(num));
return 0;
}using System;
class Solution {
public int NumberOfSteps(int num) {
if (num == 0) return 0;
return 1 + NumberOfSteps(num % 2 == 0 ? num / 2 : num - 1);
}
static void Main() {
Solution s = new Solution();
int num = 14;
Console.WriteLine("Number of steps: " + s.NumberOfSteps(num));
}
}This Python function leverages recursion to break down the number with each call, adapting functionality based on even or odd status, until zero is reached.
Time Complexity: O(log n)
Space Complexity: O(log n)
Approach 3: Default Approach
function numberOfSteps(num: number): number {
let ans = 0;
while (num) {
num = num & 1 ? num - 1 : num >>> 1;
ans++;
}
return ans;
}func numberOfSteps(num int) int {
ans := 0
for num != 0 {
if (num & 1) == 1 {
num--
} else {
num >>= 1
}
ans++
}
return ans
}impl Solution {
pub fn number_of_steps(mut num: i32) -> i32 {
let mut count = 0;
while num != 0 {
if num % 2 == 0 {
num >>= 1;
} else {
num -= 1;
}
count += 1;
}
count
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(log n) |
| Recursive Approach | Time Complexity: O(log n) |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Simulation | O(log n) | O(1) | Best general solution; minimal memory and straightforward implementation |
| Recursive Reduction | O(log n) | O(log n) | Useful for demonstrating the mathematical recurrence or practicing recursion |
Frequently asked questions
Is Number of Steps to Reduce a Number to Zero easy or hard?
Number of Steps to Reduce a Number to Zero is classified as an Easy problem. The logic is straightforward simulation, but recognizing the connection to binary representation helps explain why the algorithm runs in logarithmic time.
Number of Steps to Reduce a Number to Zero Python/Java solution
Both Python and Java implementations follow the same logic: loop while the number is not zero, increment a counter, divide by two if the number is even, otherwise subtract one. The algorithm runs in O(log n) time and constant space across all languages.
How to solve Number of Steps to Reduce a Number to Zero in O(log n)?
Use a loop that continues while the number is greater than zero. If the number is even, divide it by two; if it is odd, subtract one. Because each step either removes a binary digit or clears a bit, the algorithm runs in O(log n) time.
What is the best approach for Number of Steps to Reduce a Number to Zero?
The iterative simulation approach is the best choice. Repeatedly check if the number is even or odd, divide by 2 for even numbers, and subtract 1 for odd numbers. Each operation reduces the number quickly, resulting in O(log n) time complexity and O(1) extra space.
Is Number of Steps to Reduce a Number to Zero asked at Google/Amazon/Meta?
This problem is categorized as an easy algorithm question and has appeared in interview preparation sets for companies like Amazon and Google. It is commonly used to evaluate basic problem-solving skills and understanding of binary operations.
What data structure is used in Number of Steps to Reduce a Number to Zero?
No specialized data structure is required. The solution relies on arithmetic operations and simple control flow. The underlying concept relates to bit manipulation because dividing by two corresponds to shifting bits right in binary.
What is the time complexity of Number of Steps to Reduce a Number to Zero?
The time complexity is O(log n). Each division by 2 removes one binary digit from the number, and each subtraction clears a trailing 1 bit. Since the number of bits in n is proportional to log n, the total number of operations grows logarithmically.