Defuse the Bomb

Easy

Google

3 views

Topics:

Arrays

You have a bomb to defuse, and your time is running out! Your informer will provide you with a circular array code of length n and a key k.

To decrypt the code, you must replace every number. All the numbers are replaced simultaneously.

If k > 0, replace the i^th number with the sum of the next k numbers.
If k < 0, replace the i^th number with the sum of the previous k numbers.
If k == 0, replace the i^th number with 0.

As code is circular, the next element of code[n-1] is code[0], and the previous element of code[0] is code[n-1].

Given the circular array code and an integer key k, return the decrypted code to defuse the bomb!

Example 1:

Input: code = [5,7,1,4], k = 3
Output: [12,10,16,13]
Explanation: Each number is replaced by the sum of the next 3 numbers. The decrypted code is [7+1+4, 1+4+5, 4+5+7, 5+7+1]. Notice that the numbers wrap around.

Example 2:

Input: code = [1,2,3,4], k = 0
Output: [0,0,0,0]
Explanation: When k is zero, the numbers are replaced by 0.

Example 3:

Input: code = [2,4,9,3], k = -2
Output: [12,5,6,13]
Explanation: The decrypted code is [3+9, 2+3, 4+2, 9+4]. Notice that the numbers wrap around again. If k is negative, the sum is of the **previous** numbers.

Write a function to decrypt the code given the circular array code and the integer k.

Defuse the Bomb

Easy

Google

3 views

Topics:

Arrays

You have a bomb to defuse, and your time is running out! Your informer will provide you with a circular array code of length n and a key k.

To decrypt the code, you must replace every number. All the numbers are replaced simultaneously.

If k > 0, replace the i^th number with the sum of the next k numbers.
If k < 0, replace the i^th number with the sum of the previous k numbers.
If k == 0, replace the i^th number with 0.

As code is circular, the next element of code[n-1] is code[0], and the previous element of code[0] is code[n-1].

Given the circular array code and an integer key k, return the decrypted code to defuse the bomb!

Example 1:

Input: code = [5,7,1,4], k = 3
Output: [12,10,16,13]
Explanation: Each number is replaced by the sum of the next 3 numbers. The decrypted code is [7+1+4, 1+4+5, 4+5+7, 5+7+1]. Notice that the numbers wrap around.

Example 2:

Input: code = [1,2,3,4], k = 0
Output: [0,0,0,0]
Explanation: When k is zero, the numbers are replaced by 0.

Example 3:

Input: code = [2,4,9,3], k = -2
Output: [12,5,6,13]
Explanation: The decrypted code is [3+9, 2+3, 4+2, 9+4]. Notice that the numbers wrap around again. If k is negative, the sum is of the **previous** numbers.

Write a function to decrypt the code given the circular array code and the integer k.

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 values within the input array? Are negative numbers or zero allowed?
Can the input array be empty, or is there a guaranteed minimum length?
Is 'k' always a positive integer? What happens if 'k' is larger than the array's length?
When the bomb is defused (sum equals 'k'), should I return a boolean, the indices of the elements, or a new array containing the defused sequence?
Are there any specific error conditions that I need to handle, such as invalid input types?

Brute Force Solution

Approach

The brute force approach to defusing the bomb involves trying every single possible combination of actions in the correct order. We essentially test every possible sequence until we find one that works. It's like guessing a password by trying every single possibility.

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

Start by trying the first possible action in the sequence.
Then, try the next possible action, considering all options after the first action.
Continue this process for all remaining steps, trying every action at each step based on the previous actions taken.
For each complete sequence of actions, check if it successfully defuses the bomb.
If a sequence defuses the bomb, we found the answer. If not, we continue testing other sequences.
Keep repeating this process until we find a sequence that defuses the bomb, or until we've exhausted all possible sequences.

Code Implementation

def defuse_the_bomb_brute_force(possible_actions, is_bomb_defused):
    def generate_sequences(current_sequence):
        # Checks if the current sequence defuses the bomb
        if is_bomb_defused(current_sequence):
            return current_sequence

        if len(current_sequence) > 10:
            return None

        for action in possible_actions:
            new_sequence = current_sequence + [action]

            # Recursively tries all next possible actions
            result = generate_sequences(new_sequence)

            if result:
                return result

        return None

    # Iterates through each of the possible actions to create the first sequence
    for initial_action in possible_actions:
        sequence = [initial_action]
        solution = generate_sequences(sequence)

        # If a solution is found, the function returns it
        if solution:
            return solution

    # If no sequence defuses the bomb, return None
    return None

Big(O) Analysis

Time Complexity

O(m^n) – The brute force approach explores all possible action sequences of length n, where each action has m possible choices. Therefore, the algorithm essentially generates all possible permutations of length n from a set of m actions. This results in m options for the first action, m options for the second action, and so on, up to m options for the nth action. The total number of sequences explored will therefore be m * m * ... * m (n times), which is m^n. Thus, the time complexity is O(m^n).

Space Complexity

O(N) – The brute force approach explores all possible action sequences of length N, where N is the number of steps needed to defuse the bomb. The algorithm effectively simulates each action sequence through recursion, so the recursion stack depth can grow up to N. Therefore, the auxiliary space complexity is proportional to the maximum depth of the recursion stack, which is O(N).

Optimal Solution

Approach

The core idea is to efficiently compute a rolling sum of the code elements. We avoid recomputing sums repeatedly by updating the current sum as we move through the code, effectively sliding a window of size 'k'. This approach dramatically reduces redundant calculations.

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

First, calculate the initial sum of the first 'k' elements of the code.
Store this initial sum as the starting defused value.
Then, move one position forward in the code. Subtract the value that has left the window from the current sum.
Add the new value that has entered the window to the current sum.
Update the defused value with the new sum.
Repeat steps 3-5 until you have processed the entire code by moving through all the elements.
If 'k' is negative, process the code elements in reverse order using similar additions and subtractions to maintain the rolling sum.

Code Implementation

def defuse_the_bomb(code, k):
    number_of_elements = len(code)
    defused_code = [0] * number_of_elements

    if k == 0:
        return defused_code

    if k > 0:
        # Calculate initial sum for positive k
        current_sum = sum(code[:k])
        for i in range(number_of_elements):
            defused_code[i] = current_sum

            # Update rolling sum, wrapping around if needed
            current_sum -= code[i]
            current_sum += code[(i + k) % number_of_elements]

    else:
        # Calculate initial sum for negative k
        current_sum = sum(code[k:])

        for i in range(number_of_elements):
            defused_code[i] = current_sum
            # Update rolling sum for negative k, wrapping around if needed
            current_sum -= code[i + k]
            current_sum += code[i % number_of_elements]

    return defused_code

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the code array of size n once. Inside the loop, only constant time operations such as addition and subtraction are performed to update the rolling sum. Since the dominant operation is iterating through the array once, the time complexity is directly proportional to the size of the code array (n), resulting in O(n) time complexity.

Space Complexity

O(1) – The algorithm primarily uses a few variables to store the current sum (a single number) and potentially an index or two for looping. The defused array is created in-place overwriting the original so it's not considered auxillary space. No auxiliary data structures that scale with the input size 'n' (length of the code) are created. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Null or undefined input array	Throw an IllegalArgumentException or return null/empty list based on problem requirements to indicate invalid input.
Array with a single element	Return an empty list because a single element cannot form a pair.
Array with all elements equal to zero	Handle zeros correctly as they may or may not contribute to a valid solution depending on the problem.
Array contains extremely large positive or negative numbers potentially leading to overflow	Use appropriate data types (long, BigInteger) to avoid integer overflow during calculations.
No valid solution exists	Return an empty list or a specific error code to indicate that no combination satisfies the problem's conditions.
Array is already sorted (ascending or descending)	The solution should work correctly whether the array is sorted or not; sorting within the solution might be unnecessary.
Array size is extremely large, potentially causing memory issues	Consider using in-place algorithms or streaming techniques to minimize memory footprint.
Input array contains floating-point numbers with potential precision issues	Avoid direct equality comparisons with floating-point numbers and use a tolerance or epsilon value.