1342. Number of Steps to Reduce a Number to Zero
Problem Description
Given an integer num
, the task is to find out how many steps it would take to reduce this number to zero. The rule for each step of the reduction process is simple:
- If
num
is even, divide it by2
. - If
num
is odd, subtract1
from it.
The process is repeated until num
becomes zero and we need to count and return the total number of steps taken.
Intuition
The intuition behind the solution is to use a loop that keeps running until the number becomes zero. Inside the loop, we check if the current number is odd or even. The bitwise AND operation num & 1
is a quick way to check if a number is odd (1
) or even (0
). If the number is odd (last bit is 1
), we subtract 1
from it. If it is even (last bit is 0
), we shift the bits to the right by one position using num >>= 1
, which effectively divides the number by 2
. After each operation, we increment a counter ans
by 1 to keep track of the number of steps taken. Once the loop ends (when num
is zero), we return the counter as our result.
So, the intuition leverages simple bitwise operations for efficiency, and a while loop to iteratively reduce the number to zero, counting the steps along the way.
Learn more about Math patterns.
Solution Approach
The solution is implemented using a straightforward approach that doesn't rely on any complex algorithms or advanced data structures. The primary tools used here are bitwise operations and a loop. Here's how the implementation works:
-
We define a function
numberOfSteps
that takes an integernum
as an input and initializes a counterans
to0
. This counter will hold the total number of steps required to reducenum
to zero. -
The solution employs a
while
loop that runs as long asnum
is not zero. Within the loop, we perform one of the two operations in each iteration:- If
num
is odd (which we check using the bitwise AND operationnum & 1
), we subtract1
from it. This step ensures that an odd number becomes even, and thus can be halved in the next step. - If
num
is even, we use the right shift bitwise operationnum >>= 1
to dividenum
by2
. Bit shifting to the right by one position is synonymous with integer division by two for non-negative integers.
- If
-
After each operation inside the loop, we increment the counter
ans
by1
. This accounts for the step we've just performed. -
Once
num
is zero, the loop exits, and the function returns theans
counter, which by then has accumulated the total number of steps taken to reducenum
to zero.
The solution uses no auxiliary data structures; it only manipulates the given num
and maintains a simple integer counter. The approach is efficient both in terms of time and space complexity, as it operates in linear time with respect to the number of bits in num
and only uses a constant amount of additional space for the counter.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to clearly illustrate the solution approach using the integer 14
as our num
.
-
We call the function
numberOfSteps
withnum = 14
. -
Since the while loop condition
(num != 0)
holds true, we enter the while loop. -
We check if
14
is odd or even usingnum & 1
. Since14 & 1
equals0
,14
is even. -
We divide
14
by2
usingnum >>= 1
, which results in7
. Now,num = 7
. We incrementans
to1
. -
Since
7
is odd (7 & 1
equals1
), we subtract1
from it resulting in6
. Now,num = 6
. We incrementans
to2
. -
6
is even (6 & 1
equals0
), so we divide it by2
usingnum >>= 1
, resulting in3
. Now,num = 3
. We incrementans
to3
. -
3
is odd (3 & 1
equals1
), so we subtract1
from it, resulting in2
. Now,num = 2
. We incrementans
to4
. -
2
is even (2 & 1
equals0
), so we divide it by2
usingnum >>= 1
, yielding1
. Now,num = 1
. We incrementans
to5
. -
1
is odd (1 & 1
equals1
), so we subtract1
from it, resulting in0
. Now,num = 0
. We incrementans
to6
. -
The while loop condition
num != 0
no longer holds true, so we exit the loop. -
Finally,
numberOfSteps
returnsans
which is6
. Therefore, it takes6
steps to reduce the number14
to zero.
Here we took six steps to reduce the number from 14
to 0
. The approach involved alternating bitwise operations and arithmetic subtractions until reaching zero, tracking each operation as a step.
Solution Implementation
1class Solution:
2 def numberOfSteps(self, number: int) -> int:
3 # Initialize the step counter
4 step_count = 0
5
6 # Keep iterating until the number is reduced to zero
7 while number:
8 # Check if the current number is odd
9 if number & 1:
10 # If odd, subtract 1 from it
11 number -= 1
12 else:
13 # If even, right-shift the number (equivalent to dividing by 2)
14 number >>= 1
15 # Increment the step counter for each operation (subtract or shift)
16 step_count += 1
17
18 # Return the total number of steps taken to reduce the number to zero
19 return step_count
20
1class Solution {
2 // Method to calculate the number of steps to reduce a number to zero
3 public int numberOfSteps(int num) {
4 int steps = 0; // Counter for the number of steps taken
5
6 // Loop until the number is reduced to zero
7 while (num != 0) {
8 // If the number is odd, subtract 1, else right shift (divide by 2)
9 num = (num & 1) == 1 ? num - 1 : num >> 1;
10 // Increment the step counter
11 ++steps;
12 }
13
14 // Return the total number of steps taken
15 return steps;
16 }
17}
18
1class Solution {
2public:
3 // Function to compute the number of steps to reduce the number 'num' to zero.
4 int numberOfSteps(int num) {
5 int steps = 0; // Variable to count the number of steps taken.
6 while (num) { // Continue the process until 'num' becomes zero.
7 // If 'num' is odd, subtract 1 from it, otherwise, right shift by 1 (divide by 2).
8 num = (num & 1) ? num - 1 : num >> 1;
9 steps++; // Increment the steps counter after each operation.
10 }
11 // Return the total number of steps taken.
12 return steps;
13 }
14};
15
1/**
2 * This function returns the number of steps to reduce the number to zero.
3 * In each step, if the current number is even, you have to halve it,
4 * otherwise, you have to subtract 1 from it.
5 * @param num The number to be reduced to zero.
6 * @returns The number of steps to reduce the number to zero.
7 */
8function numberOfSteps(num: number): number {
9 let steps = 0; // Initialize the step counter to zero.
10
11 // Loop until the number is reduced to zero.
12 while (num) {
13 // If the number is odd, subtract 1 from it; if it's even, divide it by 2.
14 // This is done using bitwise operations: '&' to check if odd and '>>>' to right shift (divide by 2).
15 num = num & 1 ? num - 1 : num >>> 1;
16 steps++; // Increment the step counter.
17 }
18
19 return steps; // Return the total number of steps.
20}
21
Time and Space Complexity
The time complexity of the given code is O(log n)
. This is because each operation either decreases the number by one if it is odd or divides the number by two if it is even. In the worst-case scenario, for a number with all bits set to 1
, it will take at most 2 * log2(n)
steps to reduce the number to 0
, since each bit position would need a subtraction and a right shift to clear it.
The space complexity of the code is O(1)
since the algorithm uses a fixed amount of space. The extra space used by the algorithm does not grow with the input size n
. Only a constant number of variables (num
and ans
) are used regardless of the size of the input.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using input [30, 20, 10, 100, 33, 12]
?
1def fun(arr: List[int]) -> List[int]:
2 import heapq
3 heapq.heapify(arr)
4 res = []
5 for i in range(3):
6 res.append(heapq.heappop(arr))
7 return res
8
1public static int[] fun(int[] arr) {
2 int[] res = new int[3];
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int i = 0; i < arr.length; i++) {
5 heap.add(arr[i]);
6 }
7 for (int i = 0; i < 3; i++) {
8 res[i] = heap.poll();
9 }
10 return res;
11}
12
1class HeapItem {
2 constructor(item, priority = item) {
3 this.item = item;
4 this.priority = priority;
5 }
6}
7
8class MinHeap {
9 constructor() {
10 this.heap = [];
11 }
12
13 push(node) {
14 // insert the new node at the end of the heap array
15 this.heap.push(node);
16 // find the correct position for the new node
17 this.bubble_up();
18 }
19
20 bubble_up() {
21 let index = this.heap.length - 1;
22
23 while (index > 0) {
24 const element = this.heap[index];
25 const parentIndex = Math.floor((index - 1) / 2);
26 const parent = this.heap[parentIndex];
27
28 if (parent.priority <= element.priority) break;
29 // if the parent is bigger than the child then swap the parent and child
30 this.heap[index] = parent;
31 this.heap[parentIndex] = element;
32 index = parentIndex;
33 }
34 }
35
36 pop() {
37 const min = this.heap[0];
38 this.heap[0] = this.heap[this.size() - 1];
39 this.heap.pop();
40 this.bubble_down();
41 return min;
42 }
43
44 bubble_down() {
45 let index = 0;
46 let min = index;
47 const n = this.heap.length;
48
49 while (index < n) {
50 const left = 2 * index + 1;
51 const right = left + 1;
52
53 if (left < n && this.heap[left].priority < this.heap[min].priority) {
54 min = left;
55 }
56 if (right < n && this.heap[right].priority < this.heap[min].priority) {
57 min = right;
58 }
59 if (min === index) break;
60 [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61 index = min;
62 }
63 }
64
65 peek() {
66 return this.heap[0];
67 }
68
69 size() {
70 return this.heap.length;
71 }
72}
73
74function fun(arr) {
75 const heap = new MinHeap();
76 for (const x of arr) {
77 heap.push(new HeapItem(x));
78 }
79 const res = [];
80 for (let i = 0; i < 3; i++) {
81 res.push(heap.pop().item);
82 }
83 return res;
84}
85
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!