Jobs

Interviews

Discussions

Broken Calculator

Medium

Nutanix

4 views

Topics:

Greedy Algorithms

There is a broken calculator that has the integer startValue on its display initially. In one operation, you can:

multiply the number on display by 2, or
subtract 1 from the number on display.

Given two integers startValue and target, return the minimum number of operations needed to display target on the calculator.

Example 1:

Input: startValue = 2, target = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

Example 2:

Input: startValue = 5, target = 8
Output: 2
Explanation: Use decrement and then double {5 -> 4 -> 8}.

Example 3:

Input: startValue = 3, target = 10
Output: 3
Explanation: Use double, decrement and double {3 -> 6 -> 5 -> 10}.

Constraints:

1 <= startValue, target <= 10⁹

Try coding it in LeetCode

Broken Calculator

Medium

Nutanix

4 views

Topics:

Greedy Algorithms

There is a broken calculator that has the integer startValue on its display initially. In one operation, you can:

multiply the number on display by 2, or
subtract 1 from the number on display.

Given two integers startValue and target, return the minimum number of operations needed to display target on the calculator.

Example 1:

Input: startValue = 2, target = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

Example 2:

Input: startValue = 5, target = 8
Output: 2
Explanation: Use decrement and then double {5 -> 4 -> 8}.

Example 3:

Input: startValue = 3, target = 10
Output: 3
Explanation: Use double, decrement and double {3 -> 6 -> 5 -> 10}.

Constraints:

1 <= startValue, target <= 10⁹

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 are the maximum possible values for startValue and target?
Can startValue or target ever be zero or negative?
If it's impossible to reach the target from the startValue using the given operations, what should the function return?
Is it guaranteed that startValue and target are integers?
Should I optimize for space complexity as well as time complexity?

Brute Force Solution

Approach

The goal is to transform a starting number into a target number using only multiplication by two and subtraction by one. A brute force approach would explore every possible combination of these operations until we find the target.

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

Start with the initial number.
Consider two possible operations: multiply by two, or subtract one.
For each operation, create a new number, giving us two possibilities to explore.
Repeat this process for each new number, branching out with more possible operations.
Continue until we either reach the target number, or we've gone too far.
If we find the target number, count the number of operations it took to get there.
Do this for every possible path of operations.
Finally, choose the path that used the fewest operations to reach the target number.

Code Implementation

def broken_calculator_brute_force(start_value, target_value):
    queue = [(start_value, 0)]
    minimum_operations = float('inf')

    while queue:
        current_value, current_operations = queue.pop(0)

        # If target is found, check if it's the minimum operations
        if current_value == target_value:
            minimum_operations = min(minimum_operations, current_operations)

        # Only explore further if the current path isn't longer than the best so far
        if current_operations >= minimum_operations:
            continue

        # Optimization: Don't explore paths that go too far beyond the target
        if current_value > (target_value + 1000):
            continue

        # Check for multiplication possibility
        new_value_multiply = current_value * 2
        queue.append((new_value_multiply, current_operations + 1))

        # Check for subtraction possibility
        new_value_subtract = current_value - 1
        queue.append((new_value_subtract, current_operations + 1))

    return minimum_operations

Big(O) Analysis

Time Complexity

O(2^n) – The described brute-force approach explores all possible combinations of multiplication by two and subtraction by one. In the worst-case scenario, where the starting number is much smaller than the target, we could potentially apply a sequence of these operations repeatedly, branching out with each step. Since each number generates two new possibilities (multiply by two or subtract one), this leads to a binary tree-like exploration where the number of nodes grows exponentially with the difference between the starting number and the target number (let's denote this difference as n). Therefore, the time complexity becomes proportional to 2 raised to the power of n, resulting in O(2^n).

Space Complexity

O(2^(target - start)) – The described brute force approach explores all possible paths using recursion or an equivalent data structure like a queue. Each number generated leads to two more numbers (multiply by two, subtract by one), creating a binary tree-like structure. In the worst case, especially when the target is much larger than the start, we might explore a tree where the depth corresponds roughly to the difference between the target and the start. The number of nodes in such a binary tree grows exponentially, specifically O(2^(target - start)), representing the space needed to store intermediate numbers and the recursion call stack, or the queue for breadth-first search. Therefore, the space complexity is exponential relative to the difference between target and start numbers.

Optimal Solution

Approach

The key to solving this problem efficiently is to work backward from the target value. Instead of multiplying and subtracting from the start value, we divide and add to reach the start value, because there are only two allowed operations.

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

Start at the target number and try to reach the start number using only division by 2 and addition by 1.
If the target is larger than the start, we have to reduce it using division and addition.
If the target is even, divide it by 2. This is the fastest way to reduce it.
If the target is odd, add 1 to it. This gets us closer to being able to divide by 2.
Keep doing this (dividing if even, adding if odd) until the target is smaller than or equal to the start.
If the target is now smaller than the start, just add the difference between them to the number of operations to get the final count.
This backward approach guarantees the fewest operations because division reduces the number faster than addition increases it, and we always choose the most efficient operation possible at each step.

Code Implementation

def broken_calculator(start_value, target_value):
    number_of_operations = 0

    while target_value > start_value:
        # If target is even, divide to reduce faster
        if target_value % 2 == 0:
            target_value //= 2
            number_of_operations += 1

        # If target is odd, add 1 to make it even
        else:
            target_value += 1
            number_of_operations += 1

    # If target is smaller, add the difference
    number_of_operations += start_value - target_value

    return number_of_operations

Big(O) Analysis

Time Complexity

O(log(target)) – The algorithm works backward from the target to the start. In the worst-case scenario, where the target is a power of 2 much larger than the startValue, the primary operation is repeatedly dividing the target by 2 until it becomes less than or equal to the startValue. Each division halves the target, similar to a binary search. Therefore, the number of divisions, and hence the number of operations, is proportional to the number of times we can divide the target by 2 until we reach 1, which is log₂(target). Since addition operations are also performed within the same loop until target is less than or equal to startValue, the overall time complexity is O(log(target)).

Space Complexity

O(1) – The algorithm operates primarily on two integer variables, start and target, modifying them in place. No additional data structures like arrays, lists, or hash maps are used to store intermediate results. The space required remains constant regardless of the values of start and target. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
startValue equals target	Return 0 immediately as no operations are needed.
startValue is greater than target	Only subtraction is possible, so return startValue - target.
target is 1	Repeated subtraction is required, so return startValue - 1.
startValue and target are very large numbers potentially causing integer overflow during multiplication	Avoid direct multiplication when startValue is small and target is large, instead work backwards from target towards startValue using division and addition.
target is even, and startValue needs to be multiplied before a subtraction	Account for all possibilities of *2 and -1 while working backward from target, if possible.
startValue is 1	The optimal solution involves multiplications followed by subtractions from the multiplied values.
startValue and target are close but require a mix of multiplication and subtraction	Backtracking or BFS ensures finding the optimal path, correctly mixing *2 and -1.
Maximum recursion depth could be exceeded	Employ iterative solution with a queue, such as BFS, to avoid stack overflow.

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 are the maximum possible values for startValue and target?
Can startValue or target ever be zero or negative?
If it's impossible to reach the target from the startValue using the given operations, what should the function return?
Is it guaranteed that startValue and target are integers?
Should I optimize for space complexity as well as time complexity?

Brute Force Solution

Approach

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

Start with the initial number.
Consider two possible operations: multiply by two, or subtract one.
For each operation, create a new number, giving us two possibilities to explore.
Repeat this process for each new number, branching out with more possible operations.
Continue until we either reach the target number, or we've gone too far.
If we find the target number, count the number of operations it took to get there.
Do this for every possible path of operations.
Finally, choose the path that used the fewest operations to reach the target number.

Code Implementation

def broken_calculator_brute_force(start_value, target_value):
    queue = [(start_value, 0)]
    minimum_operations = float('inf')

    while queue:
        current_value, current_operations = queue.pop(0)

        # If target is found, check if it's the minimum operations
        if current_value == target_value:
            minimum_operations = min(minimum_operations, current_operations)

        # Only explore further if the current path isn't longer than the best so far
        if current_operations >= minimum_operations:
            continue

        # Optimization: Don't explore paths that go too far beyond the target
        if current_value > (target_value + 1000):
            continue

        # Check for multiplication possibility
        new_value_multiply = current_value * 2
        queue.append((new_value_multiply, current_operations + 1))

        # Check for subtraction possibility
        new_value_subtract = current_value - 1
        queue.append((new_value_subtract, current_operations + 1))

    return minimum_operations

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start at the target number and try to reach the start number using only division by 2 and addition by 1.
If the target is larger than the start, we have to reduce it using division and addition.
If the target is even, divide it by 2. This is the fastest way to reduce it.
If the target is odd, add 1 to it. This gets us closer to being able to divide by 2.
Keep doing this (dividing if even, adding if odd) until the target is smaller than or equal to the start.
If the target is now smaller than the start, just add the difference between them to the number of operations to get the final count.
This backward approach guarantees the fewest operations because division reduces the number faster than addition increases it, and we always choose the most efficient operation possible at each step.

Code Implementation

def broken_calculator(start_value, target_value):
    number_of_operations = 0

    while target_value > start_value:
        # If target is even, divide to reduce faster
        if target_value % 2 == 0:
            target_value //= 2
            number_of_operations += 1

        # If target is odd, add 1 to make it even
        else:
            target_value += 1
            number_of_operations += 1

    # If target is smaller, add the difference
    number_of_operations += start_value - target_value

    return number_of_operations

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
startValue equals target	Return 0 immediately as no operations are needed.
startValue is greater than target	Only subtraction is possible, so return startValue - target.
target is 1	Repeated subtraction is required, so return startValue - 1.
startValue and target are very large numbers potentially causing integer overflow during multiplication	Avoid direct multiplication when startValue is small and target is large, instead work backwards from target towards startValue using division and addition.
target is even, and startValue needs to be multiplied before a subtraction	Account for all possibilities of *2 and -1 while working backward from target, if possible.
startValue is 1	The optimal solution involves multiplications followed by subtractions from the multiplied values.
startValue and target are close but require a mix of multiplication and subtraction	Backtracking or BFS ensures finding the optimal path, correctly mixing *2 and -1.
Maximum recursion depth could be exceeded	Employ iterative solution with a queue, such as BFS, to avoid stack overflow.