Jobs

Interviews

Discussions

Integer Replacement

Medium

Asked by:

14 views

Topics:

Bit ManipulationGreedy Algorithms

Given a positive integer n, you can apply one of the following operations:

If n is even, replace n with n / 2.
If n is odd, replace n with either n + 1 or n - 1.

Return the minimum number of operations needed for n to become 1.

Example 1:

Input: n = 8
Output: 3
Explanation: 8 -> 4 -> 2 -> 1

Example 2:

Input: n = 7
Output: 4
Explanation: 7 -> 8 -> 4 -> 2 -> 1
or 7 -> 6 -> 3 -> 2 -> 1

Example 3:

Input: n = 4
Output: 2

Constraints:

1 <= n <= 2³¹ - 1

Try coding it in LeetCode

Integer Replacement

Medium

Asked by:

14 views

Topics:

Bit ManipulationGreedy Algorithms

Given a positive integer n, you can apply one of the following operations:

If n is even, replace n with n / 2.
If n is odd, replace n with either n + 1 or n - 1.

Return the minimum number of operations needed for n to become 1.

Example 1:

Input: n = 8
Output: 3
Explanation: 8 -> 4 -> 2 -> 1

Example 2:

Input: n = 7
Output: 4
Explanation: 7 -> 8 -> 4 -> 2 -> 1
or 7 -> 6 -> 3 -> 2 -> 1

Example 3:

Input: n = 4
Output: 2

Constraints:

1 <= n <= 2³¹ - 1

Try coding it in LeetCode

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 range of possible values for the input integer n?
Can the input integer n be zero or negative?
If multiple sequences of operations achieve the minimum number of steps, can I return any one of them, or is there a specific sequence I need to find?
Are there any concerns about integer overflow during intermediate calculations (e.g., when multiplying or adding)?
Can you provide a few example inputs and their expected outputs to confirm my understanding of the problem?

Brute Force Solution

Approach

To find the fewest steps to transform a number to 1, the brute force approach explores every possible path. We repeatedly apply either the rule of dividing by 2 (if the number is even) or adding or subtracting 1 (if the number is odd), until we reach 1.

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

Start with the given number.
If the number is even, divide it by 2, and remember that was one step.
If the number is odd, consider two possibilities: adding 1 or subtracting 1. Each is one step.
For each of the new numbers we got in the previous steps, apply the same rules. If even, divide by 2. If odd, consider adding or subtracting 1.
Keep doing this, branching out like a tree, until every branch reaches 1.
Count the number of steps it took to reach 1 for each branch.
Compare all the step counts from the different branches, and pick the smallest one. That's the answer.

Code Implementation

def integer_replacement_brute_force(number):    # Use a helper function for recursion. 
    def find_minimum_steps(current_number):
        if current_number == 1:
            return 0

        # If the number is even, divide by 2.
        if current_number % 2 == 0:

            return 1 + find_minimum_steps(current_number // 2)

        # Explore both addition and subtraction.
        else:

            add_one = 1 + find_minimum_steps(current_number + 1)

            subtract_one = 1 + find_minimum_steps(current_number - 1)

            # Need to choose the path with fewer steps
            return min(add_one, subtract_one)

    return find_minimum_steps(number)

Big(O) Analysis

Time Complexity

O(2^n) – The algorithm explores all possible paths by repeatedly dividing by 2 if the number is even, or adding or subtracting 1 if the number is odd. In the worst-case scenario, when the number is always odd, the algorithm branches into two possibilities (n+1 and n-1) at each step. This creates a binary tree where each level represents a step, and the number of nodes doubles at each level. Therefore, the maximum number of possible paths and operations grows exponentially with the input number n, resulting in a time complexity of O(2^n).

Space Complexity

O(2^N) – The brute force approach explores every possible path by branching out whenever the number is odd. In the worst-case scenario, where the number remains odd for a significant portion of the transformation, the algorithm effectively builds a binary tree. The depth of this tree can be proportional to the input number N, and the number of nodes in a complete binary tree of depth N can be up to 2^N. Therefore, the space used to store the function call stack and intermediate results grows exponentially with N.

Optimal Solution

Approach

The best way to solve this is to think of it like a game where you're trying to reach one in the fewest moves. The key is to make decisions based on whether the number is even or odd, focusing on getting to a power of two efficiently.

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

If the number is even, divide it by two. This is always the best move because it quickly reduces the number towards one.
If the number is odd, you have a choice: add one or subtract one. You want to choose the move that results in a number that can be divided by two as many times as possible in the future.
To pick the right move when the number is odd, look at the two numbers you'd get after adding one or subtracting one. See which resulting number has more trailing ones in its binary representation, because subtracting one will convert this to a power of two faster.
There's one special case: If the number is three, subtracting one is always the correct move. It's the only time subtracting one works best.
Keep doing these steps (dividing by two when even, or intelligently adding or subtracting one when odd) until you reach one. The number of steps you took is your answer.

Code Implementation

def integer_replacement(number):    steps_taken = 0
    while number != 1:
        if number % 2 == 0:
            number //= 2
        else:
            # Handle the odd number case

            if number == 3:
                number -= 1
            elif (number + 1) % 4 == 0:
                # Subtracting one leads to more trailing zeros
                number += 1

            else:
                # Adding one leads to more trailing zeros
                number -= 1

        steps_taken += 1
    return steps_taken

Big(O) Analysis

Time Complexity

O(log n) – The algorithm iteratively reduces the input number n towards 1. When n is even, it's divided by 2, effectively halving the number. When n is odd, either n+1 or n-1 is chosen, and in the worst case, one of these operations will at least allow the number to become even in the next step, leading to halving the number in at most two steps. Thus, the number of operations is proportional to the number of times we can divide n by 2 until we reach 1. This corresponds to the logarithm base 2 of n, resulting in a time complexity of O(log n).

Space Complexity

O(1) – The integer replacement algorithm described operates directly on the input integer and uses a constant number of variables to track the operations performed. No auxiliary data structures like lists, arrays, or hash maps are created. The space required does not scale with the input integer n, therefore the space complexity is constant.

Edge Cases

Case	How to Handle
Input n is 1	Return 0 immediately as no operations are needed.
Input n is 0	This input is invalid according to problem definition, throw an IllegalArgumentException.
Input n is Integer.MAX_VALUE	Integer.MAX_VALUE + 1 would overflow causing incorrect even/odd check; special handling needed (n = n -1, ops++) or convert to long before processing.
Input n is a large even number close to Integer.MAX_VALUE	Divide by 2 will not cause overflow, but n+1 may when trying to optimize by adding; consider decrementing instead.
Recursion depth exceeding stack limit (for recursive solutions)	Use iterative approach or memoization to avoid stack overflow errors.
Negative input n	Input is defined as a positive integer; throw IllegalArgumentException.
Input n is a power of 2	Bit manipulation can be used to efficiently solve the problem when n is a power of 2.
Values oscillating between adding and subtracting	The algorithm should choose the optimal operation (adding or subtracting 1) based on whether n+1 or n-1 has more trailing zeros after division by 2 to ensure the fewest steps.

Input n is 1

How to Handle:

Return 0 immediately as no operations are needed.

Input n is 0

How to Handle:

This input is invalid according to problem definition, throw an IllegalArgumentException.

Input n is Integer.MAX_VALUE

How to Handle:

Integer.MAX_VALUE + 1 would overflow causing incorrect even/odd check; special handling needed (n = n -1, ops++) or convert to long before processing.

Input n is a large even number close to Integer.MAX_VALUE

How to Handle:

Divide by 2 will not cause overflow, but n+1 may when trying to optimize by adding; consider decrementing instead.

Recursion depth exceeding stack limit (for recursive solutions)

How to Handle:

Use iterative approach or memoization to avoid stack overflow errors.

Negative input n

How to Handle:

Input is defined as a positive integer; throw IllegalArgumentException.

Input n is a power of 2

How to Handle:

Bit manipulation can be used to efficiently solve the problem when n is a power of 2.

Values oscillating between adding and subtracting

How to Handle:

The algorithm should choose the optimal operation (adding or subtracting 1) based on whether n+1 or n-1 has more trailing zeros after division by 2 to ensure the fewest steps.

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 range of possible values for the input integer n?
Can the input integer n be zero or negative?
If multiple sequences of operations achieve the minimum number of steps, can I return any one of them, or is there a specific sequence I need to find?
Are there any concerns about integer overflow during intermediate calculations (e.g., when multiplying or adding)?
Can you provide a few example inputs and their expected outputs to confirm my understanding of the problem?

Brute Force Solution

Approach

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

Start with the given number.
If the number is even, divide it by 2, and remember that was one step.
If the number is odd, consider two possibilities: adding 1 or subtracting 1. Each is one step.
For each of the new numbers we got in the previous steps, apply the same rules. If even, divide by 2. If odd, consider adding or subtracting 1.
Keep doing this, branching out like a tree, until every branch reaches 1.
Count the number of steps it took to reach 1 for each branch.
Compare all the step counts from the different branches, and pick the smallest one. That's the answer.

Code Implementation

def integer_replacement_brute_force(number):    # Use a helper function for recursion. 
    def find_minimum_steps(current_number):
        if current_number == 1:
            return 0

        # If the number is even, divide by 2.
        if current_number % 2 == 0:

            return 1 + find_minimum_steps(current_number // 2)

        # Explore both addition and subtraction.
        else:

            add_one = 1 + find_minimum_steps(current_number + 1)

            subtract_one = 1 + find_minimum_steps(current_number - 1)

            # Need to choose the path with fewer steps
            return min(add_one, subtract_one)

    return find_minimum_steps(number)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

If the number is even, divide it by two. This is always the best move because it quickly reduces the number towards one.
If the number is odd, you have a choice: add one or subtract one. You want to choose the move that results in a number that can be divided by two as many times as possible in the future.
To pick the right move when the number is odd, look at the two numbers you'd get after adding one or subtracting one. See which resulting number has more trailing ones in its binary representation, because subtracting one will convert this to a power of two faster.
There's one special case: If the number is three, subtracting one is always the correct move. It's the only time subtracting one works best.
Keep doing these steps (dividing by two when even, or intelligently adding or subtracting one when odd) until you reach one. The number of steps you took is your answer.

Code Implementation

def integer_replacement(number):    steps_taken = 0
    while number != 1:
        if number % 2 == 0:
            number //= 2
        else:
            # Handle the odd number case

            if number == 3:
                number -= 1
            elif (number + 1) % 4 == 0:
                # Subtracting one leads to more trailing zeros
                number += 1

            else:
                # Adding one leads to more trailing zeros
                number -= 1

        steps_taken += 1
    return steps_taken

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input n is 1	Return 0 immediately as no operations are needed.
Input n is 0	This input is invalid according to problem definition, throw an IllegalArgumentException.
Input n is Integer.MAX_VALUE	Integer.MAX_VALUE + 1 would overflow causing incorrect even/odd check; special handling needed (n = n -1, ops++) or convert to long before processing.
Input n is a large even number close to Integer.MAX_VALUE	Divide by 2 will not cause overflow, but n+1 may when trying to optimize by adding; consider decrementing instead.
Recursion depth exceeding stack limit (for recursive solutions)	Use iterative approach or memoization to avoid stack overflow errors.
Negative input n	Input is defined as a positive integer; throw IllegalArgumentException.
Input n is a power of 2	Bit manipulation can be used to efficiently solve the problem when n is a power of 2.
Values oscillating between adding and subtracting	The algorithm should choose the optimal operation (adding or subtracting 1) based on whether n+1 or n-1 has more trailing zeros after division by 2 to ensure the fewest steps.

Input n is 1

How to Handle:

Return 0 immediately as no operations are needed.

Input n is 0

How to Handle:

This input is invalid according to problem definition, throw an IllegalArgumentException.

Input n is Integer.MAX_VALUE

How to Handle:

Integer.MAX_VALUE + 1 would overflow causing incorrect even/odd check; special handling needed (n = n -1, ops++) or convert to long before processing.

Input n is a large even number close to Integer.MAX_VALUE

How to Handle:

Divide by 2 will not cause overflow, but n+1 may when trying to optimize by adding; consider decrementing instead.

Recursion depth exceeding stack limit (for recursive solutions)

How to Handle:

Use iterative approach or memoization to avoid stack overflow errors.

Negative input n

How to Handle:

Input is defined as a positive integer; throw IllegalArgumentException.

Input n is a power of 2

How to Handle:

Bit manipulation can be used to efficiently solve the problem when n is a power of 2.

Values oscillating between adding and subtracting

How to Handle:

The algorithm should choose the optimal operation (adding or subtracting 1) based on whether n+1 or n-1 has more trailing zeros after division by 2 to ensure the fewest steps.