Jobs

Interviews

Discussions

Minimum Operations to Reduce an Integer to 0

Medium

Two Sigma

1 view

Topics:

Greedy AlgorithmsBit Manipulation

You are given a positive integer n, you can do the following operation any number of times:

Add or subtract a power of 2 from n.

Return the minimum number of operations to make n equal to 0.

A number x is power of 2 if x == 2ⁱ where i >= 0.

Example 1:

Input: n = 39
Output: 3
Explanation: We can do the following operations:
- Add 2⁰ = 1 to n, so now n = 40.
- Subtract 2³ = 8 from n, so now n = 32.
- Subtract 2⁵ = 32 from n, so now n = 0.
It can be shown that 3 is the minimum number of operations we need to make n equal to 0.

Example 2:

Input: n = 54
Output: 3
Explanation: We can do the following operations:
- Add 2¹ = 2 to n, so now n = 56.
- Add 2³ = 8 to n, so now n = 64.
- Subtract 2⁶ = 64 from n, so now n = 0.
So the minimum number of operations is 3.

Constraints:

1 <= n <= 10⁵

Minimum Operations to Reduce an Integer to 0

Medium

Two Sigma

1 view

Topics:

Greedy AlgorithmsBit Manipulation

You are given a positive integer n, you can do the following operation any number of times:

Add or subtract a power of 2 from n.

Return the minimum number of operations to make n equal to 0.

A number x is power of 2 if x == 2ⁱ where i >= 0.

Example 1:

Input: n = 39
Output: 3
Explanation: We can do the following operations:
- Add 2⁰ = 1 to n, so now n = 40.
- Subtract 2³ = 8 from n, so now n = 32.
- Subtract 2⁵ = 32 from n, so now n = 0.
It can be shown that 3 is the minimum number of operations we need to make n equal to 0.

Example 2:

Input: n = 54
Output: 3
Explanation: We can do the following operations:
- Add 2¹ = 2 to n, so now n = 56.
- Add 2³ = 8 to n, so now n = 64.
- Subtract 2⁶ = 64 from n, so now n = 0.
So the minimum number of operations is 3.

Constraints:

1 <= n <= 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 integer n?
Is n guaranteed to be a positive integer, or could it be zero or negative?
If n is zero, should I return 0?
Are we optimizing for space complexity as well as time complexity?
Is there any specific power of 2 that I cannot use (e.g., should I avoid using powers of 2 that are larger than n)?

Brute Force Solution

Approach

The brute force approach for this problem is like trying every possible combination of additions and subtractions. We explore every single path, step by step, until we hit zero. It's an exhaustive search, guaranteeing we'll find the fewest steps eventually.

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

Start with the original number.
Consider two options: adding the nearest power of two that's less than or equal to the number, or subtracting the nearest power of two that's less than or equal to the number.
For each of these options, calculate the new number.
Now, for each new number, again consider the same two options: adding or subtracting the nearest power of two.
Keep repeating this process of adding or subtracting powers of two for each number you get, creating a tree of possibilities.
Whenever you reach zero, count how many additions and subtractions it took to get there. Save this count.
Once you've explored all the possible paths (or enough to be sure you've found the shortest one), compare the counts you saved. The smallest count is the answer.

Code Implementation

def minimum_operations_brute_force(number):
    minimum_operations = float('inf')

    def find_nearest_power_of_two(number_input):
        power = 0
        while (1 << power) <= number_input:
            power += 1
        return 1 << (power - 1)

    def solve(current_number, operations_count):
        nonlocal minimum_operations

        if current_number == 0:
            minimum_operations = min(minimum_operations, operations_count)
            return

        if operations_count >= minimum_operations:
            return

        nearest_power_of_two = find_nearest_power_of_two(current_number)

        # Explore adding the nearest power of two
        solve(current_number - nearest_power_of_two, operations_count + 1)

        # Explore subtracting the nearest power of two
        solve(current_number + nearest_power_of_two, operations_count + 1)

    # Start the recursive search
    solve(number, 0)

    return minimum_operations

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^log(n)) – The described brute force approach explores a binary tree of possibilities. The height of this tree is proportional to log(n), where n is the input number, because in each step we are subtracting or adding a power of 2, effectively halving the remaining distance to 0 in the best-case scenario. Since each node in the tree has two children (representing addition and subtraction), the number of nodes grows exponentially with the height of the tree, resulting in a time complexity of approximately O(2^log(n)). The base of the logarithm is 2 since we are dealing with powers of 2.

Space Complexity

O(2^logN) – The brute force approach explores all possible paths of adding or subtracting the nearest power of two until the number reaches zero. This exploration can be visualized as a binary tree where each node represents a number and each branch represents either adding or subtracting a power of two. The height of this tree can be at most logN, where N is the input number, because at each step, we are approximately halving the number. Since the tree is binary, the maximum number of nodes at level k is 2^k. Therefore, the space complexity, representing the maximum number of nodes we might need to store in the recursion call stack at any time, is proportional to the maximum number of nodes that might appear across all levels of the binary tree which can be up to O(2^logN).

Optimal Solution

Approach

The key insight is to recognize the number's binary representation. We want to strategically add or subtract powers of two to efficiently reach zero.

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

Think of the number as a sum of powers of two, represented by its binary form.
Look at groups of consecutive '1's in the binary representation.
If a group of consecutive '1's is shorter than or equal to the number of digits to its right, it is better to subtract that group's value from the number.
However, if a group of consecutive '1's is longer than the number of digits to its right, it's more efficient to add a power of two so you can turn those ones into zeros, at the cost of adding another one at the spot just after the last '1'.
Continue this process, working through the binary representation until the number is reduced to zero. Each addition or subtraction is one operation.
The total number of additions and subtractions used is the minimum number of operations.

Code Implementation

def minimum_operations_to_reduce_integer_to_zero(number):
    operations_count = 0
    while number > 0:
        least_significant_bit = number & 1

        if least_significant_bit == 0:
            number >>= 1
            operations_count += 1
        else:
            # Find the length of consecutive ones
            consecutive_ones_length = 0
            temp_number = number
            while (temp_number & 1) == 1:
                consecutive_ones_length += 1
                temp_number >>= 1

            # Check if it is more efficient to add or subtract
            if consecutive_ones_length == 1 or (number >> consecutive_ones_length) & 1 == 0:
                number -= (1 << (consecutive_ones_length - 1))

                number >>= (consecutive_ones_length - 1)

                operations_count += consecutive_ones_length

            else:

                #It is more efficient to add a power of two
                number += (1 << consecutive_ones_length) - (1 << (consecutive_ones_length - 1))

                number >>= consecutive_ones_length

                operations_count += consecutive_ones_length

    return operations_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(log n) – The core of the algorithm revolves around examining the binary representation of the input integer, n. The number of bits in the binary representation is proportional to log n. The algorithm iterates through these bits, making a decision (addition or subtraction) at each step based on consecutive ones. Therefore, the runtime is directly proportional to the number of bits, resulting in a time complexity of O(log n).

Space Complexity

O(log N) – The primary driver of space complexity is the conversion of the input integer N to its binary representation. The length of the binary representation is proportional to log N, where N is the input integer. Thus, implicitly storing the binary representation requires space proportional to log N. No other significant auxiliary space is used beyond this representation.

Edge Cases

Case	How to Handle
n is 0	Return 0, as no operations are needed.
n is 1	Return 1, as one subtraction operation is needed (1 - 2^0).
n is a power of 2 (e.g., n = 2, 4, 8, 16)	Return 1, as one subtraction operation is needed (n - 2^k where 2^k = n).
n is a large number (close to the maximum integer value)	The solution should scale efficiently, likely using dynamic programming or a greedy approach with logarithmic complexity, to avoid exceeding time limits.
n is slightly larger than a power of 2 (e.g., n = 9, slightly bigger than 8 = 2^3)	The algorithm correctly considers both adding and subtracting powers of 2 in these cases to find the minimum operations.
Integer overflow when calculating powers of 2	Ensure powers of 2 are calculated and stored appropriately to prevent overflows, consider using a long integer type.
Negative input values	The problem states that n is a positive integer, so throw an exception or return an appropriate error code to handle invalid input.
Multiple possible valid solutions	The algorithm aims to find one valid solution, the one with the minimum number of operations, and returns that value.

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 integer n?
Is n guaranteed to be a positive integer, or could it be zero or negative?
If n is zero, should I return 0?
Are we optimizing for space complexity as well as time complexity?
Is there any specific power of 2 that I cannot use (e.g., should I avoid using powers of 2 that are larger than n)?

Brute Force Solution

Approach

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

Start with the original number.
Consider two options: adding the nearest power of two that's less than or equal to the number, or subtracting the nearest power of two that's less than or equal to the number.
For each of these options, calculate the new number.
Now, for each new number, again consider the same two options: adding or subtracting the nearest power of two.
Keep repeating this process of adding or subtracting powers of two for each number you get, creating a tree of possibilities.
Whenever you reach zero, count how many additions and subtractions it took to get there. Save this count.
Once you've explored all the possible paths (or enough to be sure you've found the shortest one), compare the counts you saved. The smallest count is the answer.

Code Implementation

def minimum_operations_brute_force(number):
    minimum_operations = float('inf')

    def find_nearest_power_of_two(number_input):
        power = 0
        while (1 << power) <= number_input:
            power += 1
        return 1 << (power - 1)

    def solve(current_number, operations_count):
        nonlocal minimum_operations

        if current_number == 0:
            minimum_operations = min(minimum_operations, operations_count)
            return

        if operations_count >= minimum_operations:
            return

        nearest_power_of_two = find_nearest_power_of_two(current_number)

        # Explore adding the nearest power of two
        solve(current_number - nearest_power_of_two, operations_count + 1)

        # Explore subtracting the nearest power of two
        solve(current_number + nearest_power_of_two, operations_count + 1)

    # Start the recursive search
    solve(number, 0)

    return minimum_operations

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The key insight is to recognize the number's binary representation. We want to strategically add or subtract powers of two to efficiently reach zero.

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

Think of the number as a sum of powers of two, represented by its binary form.
Look at groups of consecutive '1's in the binary representation.
If a group of consecutive '1's is shorter than or equal to the number of digits to its right, it is better to subtract that group's value from the number.
However, if a group of consecutive '1's is longer than the number of digits to its right, it's more efficient to add a power of two so you can turn those ones into zeros, at the cost of adding another one at the spot just after the last '1'.
Continue this process, working through the binary representation until the number is reduced to zero. Each addition or subtraction is one operation.
The total number of additions and subtractions used is the minimum number of operations.

Code Implementation

def minimum_operations_to_reduce_integer_to_zero(number):
    operations_count = 0
    while number > 0:
        least_significant_bit = number & 1

        if least_significant_bit == 0:
            number >>= 1
            operations_count += 1
        else:
            # Find the length of consecutive ones
            consecutive_ones_length = 0
            temp_number = number
            while (temp_number & 1) == 1:
                consecutive_ones_length += 1
                temp_number >>= 1

            # Check if it is more efficient to add or subtract
            if consecutive_ones_length == 1 or (number >> consecutive_ones_length) & 1 == 0:
                number -= (1 << (consecutive_ones_length - 1))

                number >>= (consecutive_ones_length - 1)

                operations_count += consecutive_ones_length

            else:

                #It is more efficient to add a power of two
                number += (1 << consecutive_ones_length) - (1 << (consecutive_ones_length - 1))

                number >>= consecutive_ones_length

                operations_count += consecutive_ones_length

    return operations_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n is 0	Return 0, as no operations are needed.
n is 1	Return 1, as one subtraction operation is needed (1 - 2^0).
n is a power of 2 (e.g., n = 2, 4, 8, 16)	Return 1, as one subtraction operation is needed (n - 2^k where 2^k = n).
n is a large number (close to the maximum integer value)	The solution should scale efficiently, likely using dynamic programming or a greedy approach with logarithmic complexity, to avoid exceeding time limits.
n is slightly larger than a power of 2 (e.g., n = 9, slightly bigger than 8 = 2^3)	The algorithm correctly considers both adding and subtracting powers of 2 in these cases to find the minimum operations.
Integer overflow when calculating powers of 2	Ensure powers of 2 are calculated and stored appropriately to prevent overflows, consider using a long integer type.
Negative input values	The problem states that n is a positive integer, so throw an exception or return an appropriate error code to handle invalid input.
Multiple possible valid solutions	The algorithm aims to find one valid solution, the one with the minimum number of operations, and returns that value.