Jobs

Interviews

Discussions

Number of Steps to Reduce a Number to Zero

Easy

Hudson River Trading

0 views

Topics:

Bit Manipulation

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 <= 10⁶

Number of Steps to Reduce a Number to Zero

Easy

Hudson River Trading

0 views

Topics:

Bit Manipulation

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 <= 10⁶

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible value of the input number `num`?
Is the input always a non-negative integer, or should I handle other data types like negative numbers or decimals?
Are there any specific performance considerations given the possible range of `num`?
Are we optimizing for space complexity, or is time complexity the primary concern?
If the input is zero, should I return zero immediately, or is there some other expected behavior?

Brute Force Solution

Approach

We want to find the fewest operations to turn a number into zero. A brute force approach means we'll try every possible operation, one at a time, until we reach zero, keeping track of the steps.

Here's how the algorithm would work step-by-step:

Start with the number you're given.
Check if the number is even. If it is, divide it by two and increase the step count by one.
If the number is odd, either subtract one from it, or add one to it. We will explore BOTH possibilties.
For both possibilities after dealing with an odd number, increase the step count by one.
After the subtraction or addition, you will have a new number. Repeat the even/odd check on that new number.
Continue doing this until you end up with zero for BOTH possibilities.
Count the total number of steps it took for each possibility (adding or subtracting 1).
Choose the path (adding or subtracting 1 when the number is odd) that took the fewest steps to reach zero. That's our answer.

Code Implementation

def steps_to_zero_brute_force(number):
    # Use a helper function to explore the possible paths.
    def calculate_steps(current_number, step_count):
        if current_number == 0:
            return step_count

        if current_number % 2 == 0:
            # If even, divide by 2 and increment step count.
            return calculate_steps(current_number // 2, step_count + 1)
        else:
            # Explore both adding and subtracting one.

            subtract_one_steps = calculate_steps(current_number - 1, step_count + 1)

            add_one_steps = calculate_steps(current_number + 1, step_count + 1)

            # Choose the path with the minimum steps.
            return min(subtract_one_steps, add_one_steps)

    # Initiate the recursive calls
    return calculate_steps(number, 0)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^n) – The algorithm explores two possibilities (add or subtract 1) for each odd number encountered. In the worst-case scenario, the number is always odd. If the input number is n, the algorithm branches into two paths at each step effectively creating a binary tree of possibilities. The depth of this tree is proportional to n, and in the worst case, we explore all paths, which results in 2^n operations. Therefore, the time complexity is O(2^n).

Space Complexity

O(N) – The provided algorithm, as described, involves exploring two possibilities when encountering an odd number, effectively branching the computation. This branching continues recursively until zero is reached for both possibilities. Therefore, the algorithm implicitly builds a binary tree of possible computations. The maximum depth of this tree is proportional to the input number N because, in the worst-case scenario, we might have to add or subtract 1 and then repeatedly divide by 2, or repeatedly add or subtract 1. This means the space used for storing intermediate results and the recursion call stack scales linearly with N. Thus, the space complexity is O(N).

Optimal Solution

Approach

This problem asks us to figure out the fewest operations needed to reach zero. The key idea is to look at whether the number is even or odd and then decide what to do based on that. By consistently applying the correct operation, we quickly get to zero.

Here's how the algorithm would work step-by-step:

Check if the number is zero. If it is, we're done and no steps are needed.
If the number is even, divide it by two. This is because dividing by two is always the fastest way to make an even number smaller.
If the number is odd, subtract one from it. This is because subtracting one makes it even, and then we can divide by two in the next step.
Keep repeating steps two and three until the number becomes zero. Keep track of how many steps you take.

Code Implementation

def number_of_steps_to_zero(number):
    steps_count = 0

    while number > 0:
        # Even numbers benefit from division.
        if number % 2 == 0:

            number /= 2
            steps_count += 1

        else:
            # Odd numbers require subtraction to become even.
            number -= 1

            steps_count += 1

    return steps_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(log n) – The input is a number, and the operations performed depend on whether the number is even or odd. Each even number is divided by 2, and each odd number is reduced by 1 before potentially being divided by 2 in the next step. This halving of the number in each iteration (or two iterations in the worst case when the number is odd) means the number of steps is proportional to the number of times the input number can be divided by 2 until it reaches 0 or 1. This is a logarithmic relationship, so the time complexity is O(log n).

Space Complexity

O(1) – The algorithm uses a constant amount of extra space. We only use a counter variable to track the number of steps. The space required for this counter does not depend on the input number N. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Input is zero	Return 0 immediately as no steps are needed to reduce 0 to 0.
Input is a small positive integer (e.g., 1, 2, 3)	The algorithm should correctly calculate the steps for these basic cases.
Input is a large positive integer	Ensure the solution does not cause integer overflow during division or subtraction, using appropriate data types.
Input is a power of 2 (e.g., 8, 16, 32)	The algorithm should efficiently handle powers of 2 by repeatedly dividing by 2.
Input is an odd number close to a power of 2 (e.g., 15, 31, 63)	The solution must properly alternate subtraction and division for these numbers.
Integer overflow if steps get too large	Use a 64-bit integer type (long) to store the number of steps to avoid potential overflow issues.
Negative Input	The prompt specifies a non-negative integer; the solution should throw an exception or return an error code if the input is negative.
Maximum integer value	Test with the maximum integer value to make sure intermediate calculations do not overflow, using data types that can handle the calculations.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible value of the input number `num`?
Is the input always a non-negative integer, or should I handle other data types like negative numbers or decimals?
Are there any specific performance considerations given the possible range of `num`?
Are we optimizing for space complexity, or is time complexity the primary concern?
If the input is zero, should I return zero immediately, or is there some other expected behavior?

Brute Force Solution

Approach

We want to find the fewest operations to turn a number into zero. A brute force approach means we'll try every possible operation, one at a time, until we reach zero, keeping track of the steps.

Here's how the algorithm would work step-by-step:

Start with the number you're given.
Check if the number is even. If it is, divide it by two and increase the step count by one.
If the number is odd, either subtract one from it, or add one to it. We will explore BOTH possibilties.
For both possibilities after dealing with an odd number, increase the step count by one.
After the subtraction or addition, you will have a new number. Repeat the even/odd check on that new number.
Continue doing this until you end up with zero for BOTH possibilities.
Count the total number of steps it took for each possibility (adding or subtracting 1).
Choose the path (adding or subtracting 1 when the number is odd) that took the fewest steps to reach zero. That's our answer.

Code Implementation

def steps_to_zero_brute_force(number):
    # Use a helper function to explore the possible paths.
    def calculate_steps(current_number, step_count):
        if current_number == 0:
            return step_count

        if current_number % 2 == 0:
            # If even, divide by 2 and increment step count.
            return calculate_steps(current_number // 2, step_count + 1)
        else:
            # Explore both adding and subtracting one.

            subtract_one_steps = calculate_steps(current_number - 1, step_count + 1)

            add_one_steps = calculate_steps(current_number + 1, step_count + 1)

            # Choose the path with the minimum steps.
            return min(subtract_one_steps, add_one_steps)

    # Initiate the recursive calls
    return calculate_steps(number, 0)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Check if the number is zero. If it is, we're done and no steps are needed.
If the number is even, divide it by two. This is because dividing by two is always the fastest way to make an even number smaller.
If the number is odd, subtract one from it. This is because subtracting one makes it even, and then we can divide by two in the next step.
Keep repeating steps two and three until the number becomes zero. Keep track of how many steps you take.

Code Implementation

def number_of_steps_to_zero(number):
    steps_count = 0

    while number > 0:
        # Even numbers benefit from division.
        if number % 2 == 0:

            number /= 2
            steps_count += 1

        else:
            # Odd numbers require subtraction to become even.
            number -= 1

            steps_count += 1

    return steps_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input is zero	Return 0 immediately as no steps are needed to reduce 0 to 0.
Input is a small positive integer (e.g., 1, 2, 3)	The algorithm should correctly calculate the steps for these basic cases.
Input is a large positive integer	Ensure the solution does not cause integer overflow during division or subtraction, using appropriate data types.
Input is a power of 2 (e.g., 8, 16, 32)	The algorithm should efficiently handle powers of 2 by repeatedly dividing by 2.
Input is an odd number close to a power of 2 (e.g., 15, 31, 63)	The solution must properly alternate subtraction and division for these numbers.
Integer overflow if steps get too large	Use a 64-bit integer type (long) to store the number of steps to avoid potential overflow issues.
Negative Input	The prompt specifies a non-negative integer; the solution should throw an exception or return an error code if the input is negative.
Maximum integer value	Test with the maximum integer value to make sure intermediate calculations do not overflow, using data types that can handle the calculations.