Skip to main content

Defuse the Bomb Solution

In this tutorial, we will solve the Defuse the Bomb problem using a circular array and sliding window approach. We will provide the implementation of the solution in C++, Java, and Python.

Problem Description​

You have a bomb to defuse, and 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 as follows:

  • 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].

Examples​

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.

Constraints​

  • n == code.length
  • 1 <= n <= 100
  • 1 <= code[i] <= 100
  • -(n - 1) <= k <= n - 1

Solution for Defuse the Bomb Problem​

Intuition and Approach​

The problem can be solved using a sliding window approach to handle the circular nature of the array. Depending on the value of k, we sum the appropriate elements and use modular arithmetic to handle the circular behavior.

Approach 1: Brute Force (Naive)​

The brute force approach involves iterating through each element and calculating the sum of the next or previous k elements based on the value of k.

Code in Different Languages​

Written by @ImmidiSivani
class Solution {
public:
vector<int> decrypt(vector<int>& code, int k) {
int n = code.size();
vector<int> result(n, 0);

if (k == 0) return result;

for (int i = 0; i < n; ++i) {
int sum = 0;
for (int j = 1; j <= abs(k); ++j) {
if (k > 0) {
sum += code[(i + j) % n];
} else {
sum += code[(i - j + n) % n];
}
}
result[i] = sum;
}

return result;
}
};

Complexity Analysis​

  • Time Complexity: O(n⋅∣k∣)O(n \cdot |k|) due to nested loops.
  • Space Complexity: O(n)O(n) for the result array.
  • Where n is the length of the code array.
  • The time complexity is O(n⋅∣k∣)O(n \cdot |k|) because we iterate through each element and calculate the sum of k elements.
  • The space complexity is O(n)O(n) because we store the result in a new array.

Authors:

Loading...