Defuse the Bomb — Solution in Python, Java & C++
Defuse the Bomb solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays and simulation.
Defuse the Bomb is an easy coding problem on arrays, simulation and sliding window, asked in Amazon, Microsoft and Wipro interviews.
- Difficulty: Easy
- Topics: Arrays, Simulation, Sliding Window
- Asked at: Amazon, Microsoft, Wipro
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
The bomb's code is a circular array. To defuse it, replace every number simultaneously:
- if
k > 0, with the sum of the nextknumbers; - if
k < 0, with the sum of the previous|k|numbers; - if
k == 0, with0.
Return the decrypted array.
Example 1
Input: code = [5,7,1,4], k = 3
Output: [12,10,16,13]
Explanation: Index 0 takes 7+1+4; the circle wraps for the rest.
Example 2
Input: code = [1,2,3,4], k = 0
Output: [0,0,0,0]
Example 3
Input: code = [2,4,9,3], k = -2
Output: [12,5,6,13]
Explanation: Index 0 takes the previous two, which wrap to 9 and 3.
Constraints
1 <= code.length <= 1001 <= code[i] <= 100-code.length < k < code.length
Hints for Defuse the Bomb
Hint 1
The replacements happen simultaneously, so read from the original array and write to a new one.
Hint 2
Modular indexing handles the wrap:
(i + t) % ngoing forward,((i - t) % n + n) % ngoing back.Hint 3
A sliding window of size
|k|also works and is what the problem is named after.
How to solve Defuse the Bomb
For each index, sum the |k| neighbours on the appropriate side, wrapping with modular arithmetic. At n <= 100 the direct double loop is already fast enough; a rolling window makes it linear.
Approach
- Allocate a fresh output array so the reads always see the original values.
k == 0returns all zeros.- For
k > 0, sumcode[(i + t) % n]fortin1 … k; fork < 0, sumcode[((i - t) % n + n) % n]fortin1 … |k|.
Why it works
The circular index formula maps any offset back into range, and the extra + n before the second modulo fixes languages where % on a negative operand yields a negative result. Writing into a separate array is what makes the replacement simultaneous — updating in place would feed already-decrypted values into later sums.
Complexity
- Time —
O(n · |k|), or O(n) with a rolling window - Space —
O(n)
Pitfalls
- Updating
codein place corrupts the later sums. - In C, Java, Go and JavaScript,
-1 % nis negative — normalise before indexing. - The current element is never included; the offsets start at 1.
Reference solution
Python
from typing import List
def decrypt(code: List[int], k: int) -> List[int]:
n = len(code)
out = [0] * n
if k == 0:
return out
for i in range(n):
total = 0
if k > 0:
for t in range(1, k + 1):
total += code[(i + t) % n]
else:
for t in range(1, -k + 1):
total += code[(i - t) % n]
out[i] = total
return outJava
public static int[] decrypt(int[] code, int k) {
int n = code.length;
int[] out = new int[n];
if (k == 0) return out;
for (int i = 0; i < n; i++) {
int sum = 0;
if (k > 0) {
for (int t = 1; t <= k; t++) sum += code[(i + t) % n];
} else {
for (int t = 1; t <= -k; t++) sum += code[((i - t) % n + n) % n];
}
out[i] = sum;
}
return out;
}C++
vector<int> decrypt(vector<int>& code, int k) {
int n = (int) code.size();
vector<int> out(n, 0);
if (k == 0) return out;
for (int i = 0; i < n; i++) {
int sum = 0;
if (k > 0) {
for (int t = 1; t <= k; t++) sum += code[(i + t) % n];
} else {
for (int t = 1; t <= -k; t++) sum += code[((i - t) % n + n) % n];
}
out[i] = sum;
}
return out;
}JavaScript
var decrypt = function(code, k) {
var n = code.length;
var out = [];
for (var t = 0; t < n; t++) out.push(0);
if (k === 0) return out;
for (var i = 0; i < n; i++) {
var sum = 0, j;
if (k > 0) {
for (j = 1; j <= k; j++) sum += code[(i + j) % n];
} else {
for (j = 1; j <= -k; j++) sum += code[((i - j) % n + n) % n];
}
out[i] = sum;
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sliding Window Technique