algoadvance

Leetcode Problem 1652: Defuse the Bomb

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 deactivate the bomb, you must replace every number in the code array with a new number. The new number at position i will be obtained by summing the next k numbers in the code (if k is positive) or the previous k numbers (if k is negative). If k is zero, the new numbers will be all zeros.

Since the array is circular, if k is positive, the sum of the next k numbers will wrap around to the beginning of the array; if k is negative, the sum of the previous k numbers will wrap around to the end of the array.

You need to return the transformed array to stop the bomb from exploding.

Example 1:

Input: code = [5,7,1,4], k = 3
Output: [12,10,16,13]
Explanation: Each element in the output array is obtained by summing the next 3 elements in the circular array.

Example 2:

Input: code = [1,2,3,4], k = 0
Output: [0,0,0,0]
Explanation: When k is 0, all elements in the output array are 0.

Example 3:

Input: code = [2,4,9,3], k = -2
Output: [12,5,6,13]
Explanation: When k is negative, the sum of the previous 2 elements is returned.

Clarifying Questions:

  1. Is the input array always non-empty?
    • Yes, according to the problem constraints.
  2. Is the value of k guaranteed to be within a specific range?
    • Yes, k is within the range [-n, n] where n is the length of the code array.
  3. Should we consider k = 0 as a special case?
    • Yes, if k = 0, we return an array of the same length with all zeros.

Strategy:

  1. Handling k = 0:
    • Directly return an array of zeros of the same length as code.
  2. Handling positive k:
    • For each index i, sum the next k elements wrapping around the array using modulo arithmetic.
  3. Handling negative k:
    • For each index i, sum the previous k elements wrapping around the array using modulo arithmetic.

Code:

def decrypt(code, k):
    n = len(code)
    result = [0] * n
    
    if k == 0:
        return result
    
    for i in range(n):
        if k > 0:
            result[i] = sum(code[(i+j+1) % n] for j in range(k))
        else:
            result[i] = sum(code[(i+j) % n] for j in range(k, 0))
    
    return result

# Example Usage
print(decrypt([5, 7, 1, 4], 3)) # Output: [12, 10, 16, 13]
print(decrypt([1, 2, 3, 4], 0)) # Output: [0, 0, 0, 0]
print(decrypt([2, 4, 9, 3], -2)) # Output: [12, 5, 6, 13]

Time Complexity:

Given that k is within the range [-n, n], this is an efficient approach consistent with the problem constraints.

Feel free to run the code with the examples provided to verify its correctness!

Try our interview co-pilot at AlgoAdvance.com