# Number of Steps to Reduce a Number to Zero
**Difficulty:** EASY
[External](https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero)
Canonical: https://scaleengineer.com/dsa/problems/number-of-steps-to-reduce-a-number-to-zero
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Companies:** [Hudson River Trading](https://scaleengineer.com/companies/hudson-river-trading)
---
## 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`

# Approaches
## Iterative Simulation
This approach directly simulates the process described in the problem statement. We use a loop that continues as long as the number is greater than zero. Inside the loop, we check if the number is even or odd and perform the corresponding operation (divide by 2 or subtract 1). We increment a counter in each iteration to keep track of the steps.
**Time:** O(log n) - The value of `num` is reduced by at least half in every two steps. For an even number, it's halved in one step. For an odd number, it becomes even in one step and is then halved in the next. The number of operations is therefore proportional to the number of bits in the binary representation of `num`, which is `log2(num)`. · **Space:** O(1) - We only use a few variables to store the current number and the step count, which requires constant extra space regardless of the input size.
**Pros:** Very simple to understand and implement as it directly translates the problem description into code.; It is guaranteed to be correct and works for all non-negative integers.
**Cons:** Slightly less performant than the bit manipulation approach due to the overhead of the loop and conditional checks in each iteration.
### Explanation
The most straightforward way to solve this problem is to follow the instructions literally. We can set up a loop that runs until our number becomes zero. In each step of the loop, we check if the current number is even or odd.

- If the number is even, we divide it by 2.
- If the number is odd, we subtract 1 from it.

We use a counter variable, initialized to zero, and increment it for every operation we perform. The loop terminates when the number reaches zero, and we return the value of the counter.

This can be implemented using standard arithmetic operators (`%` for modulo and `/` for division) or slightly more efficient bitwise operators (`&` to check for odd/even and `>>` for division by 2).

```java
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;
    }
}
```

Here is the version with bitwise operators, which is typically faster at the machine level:

```java
class Solution {
    public int numberOfSteps(int num) {
        int steps = 0;
        while (num > 0) {
            if ((num & 1) == 0) { // Check if the last bit is 0 (even)
                num >>= 1;      // Right shift by 1 (divide by 2)
            } else {
                num--;          // Subtract 1
            }
            steps++;
        }
        return steps;
    }
}
```
### Algorithm
- Initialize a variable `steps` to 0.
- If `num` is 0, return 0.
- Loop while `num` is greater than 0:
  - If `num` is even (i.e., `num % 2 == 0`), update `num` by dividing it by 2 (`num = num / 2`).
  - Else (if `num` is odd), update `num` by subtracting 1 from it (`num = num - 1`).
  - Increment the `steps` counter in each iteration.
- After the loop terminates, return the total `steps`.

## Bit Manipulation and Direct Calculation
This approach analyzes the problem from a binary representation perspective. By observing the effect of the operations on the bits of the number, we can derive a mathematical formula to calculate the number of steps directly. This avoids the simulation loop and leads to a highly efficient, constant-time solution.
**Time:** O(1) - The built-in functions `Integer.bitCount` and `Integer.numberOfLeadingZeros` are typically implemented using single, fast hardware instructions. Therefore, the calculation is independent of the magnitude of `num` (for a fixed-size integer type) and executes in constant time. · **Space:** O(1) - This approach uses a fixed number of variables. The built-in functions operate in constant space. (Note: `Integer.toBinaryString` would technically use O(log n) space for the string, but the version with `numberOfLeadingZeros` is purely O(1)).
**Pros:** Extremely fast and efficient, as it computes the result directly without loops.; Provides a deeper understanding of the problem at the bit level.
**Cons:** The logic is less intuitive and requires understanding binary arithmetic.; It relies on built-in functions whose implementation details might not be obvious to everyone.
### Explanation
A deeper look at the operations reveals a pattern related to the number's binary form.

- **Dividing by 2**: This is equivalent to a right bit shift (`>> 1`). This operation is performed when the number is even, i.e., its least significant bit (LSB) is `0`.
- **Subtracting 1**: This is performed when the number is odd (LSB is `1`). Subtracting 1 from an odd number flips its LSB from `1` to `0`, making it even. The next operation will then be a division by 2.

Let's analyze the cost per bit:
- A `0` bit at the end of the binary string requires one step (division/right shift) to be removed.
- A `1` bit at the end requires two steps: one step to subtract 1 (making it `0`), and another step to divide by 2 (right shift). The only exception is the most significant bit (MSB), which, when it becomes the number `1`, only requires one subtraction step to become `0`.

This leads to a formula: the total steps are the sum of steps for each bit. Each `0` contributes 1 step, and each `1` contributes 2 steps, minus 1 for the final step on the MSB.
Total Steps = `(number of 0s) * 1 + (number of 1s) * 2 - 1`
Let `L` be the length of the binary string and `P` be the population count (number of 1s). The number of 0s is `L - P`.
Total Steps = `(L - P) + 2*P - 1 = L + P - 1`.

So, the formula is: `(length of binary representation) + (number of set bits) - 1`.

For a positive number `num`, the length of its binary representation is `floor(log2(num)) + 1` and the number of set bits is its population count.

```java
class Solution {
    public int numberOfSteps(int num) {
        if (num == 0) {
            return 0;
        }
        // Using Integer.toBinaryString() to get length and Integer.bitCount() for set bits.
        String binaryString = Integer.toBinaryString(num);
        int length = binaryString.length();
        int setBits = Integer.bitCount(num);
        return length + setBits - 1;
    }
}
```

For maximum performance, we can avoid string conversion by using other bitwise intrinsics:

```java
class Solution {
    public int numberOfSteps(int num) {
        if (num == 0) {
            return 0;
        }
        // Length of binary string for a 32-bit int is 32 - numberOfLeadingZeros.
        int length = 32 - Integer.numberOfLeadingZeros(num);
        int setBits = Integer.bitCount(num);
        return length + setBits - 1;
    }
}
```
### Algorithm
- Handle the edge case: if `num` is 0, return 0.
- Calculate the number of set bits (1s) in the binary representation of `num`. In Java, this is `Integer.bitCount(num)`.
- Calculate the length of the binary representation of `num`. This can be found using `Integer.toBinaryString(num).length()` or more efficiently `32 - Integer.numberOfLeadingZeros(num)`.
- The total number of steps is given by the formula: `(length of binary string) + (number of set bits) - 1`.
- Return this calculated value.

# Solutions
### Java

```java
class Solution {
public
  int numberOfSteps(int num) {
    int ans = 0;
    while (num != 0) {
      num = (num & 1) == 1 ? num - 1 : num >> 1;
      ++ans;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numberOfSteps(int num) {
    int ans = 0;
    while (num) {
      num = num & 1 ? num - 1 : num >> 1;
      ++ans;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numberOfSteps(self, num: int) -> int: ans = 0 while num: if num & 1: num -= 1 else: num >>= 1 ans += 1 return ans

```