1652. Defuse the Bomb
Description
You have a bomb to defuse, and your time is running out! Your informer will provide you with a circular array code
of length of n
and a key k
.
To decrypt the code, you must replace every number. All the numbers are replaced simultaneously.
- If
k > 0
, replace theith
number with the sum of the nextk
numbers. - If
k < 0
, replace theith
number with the sum of the previousk
numbers. - If
k == 0
, replace theith
number with0
.
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.
Constraints:
n == code.length
1 <= n <= 100
1 <= code[i] <= 100
-(n - 1) <= k <= n - 1
Solutions
Solution 1: Simulation
We define an answer array ans
of length n
, initially all elements are 0
. According to the problem, if k
is 0
, return ans
directly.
Otherwise, we traverse each position i
:
- If
k
is a positive number, then the value at positioni
is the sum of the values at thek
positions after positioni
, that is:
$$ ans[i] = \sum_{j=i+1}^{i+k} code[j \bmod n] $$
- If
k
is a negative number, then the value at positioni
is the sum of the values at the|k|
positions before positioni
, that is:
$$ ans[i] = \sum_{j=i+k}^{i-1} code[(j+n) \bmod n] $$
The time complexity is $O(n \times |k|)$, ignoring the space consumption of the answer, the space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
Solution 2: Prefix Sum
In Solution 1, for each position $i$, we need to traverse $k$ positions, which involves a lot of repeated calculations. We can optimize this by using prefix sums.
We duplicate the code
array (this can be achieved without actually duplicating the array, but by cyclically traversing with modulo operation), resulting in an array of twice the length. We then calculate the prefix sum of this array, resulting in a prefix sum array $s$ of length $2 \times n + 1$.
If $k$ is a positive number, then the value at position $i$ is the sum of the values at the $k$ positions after position $i$, i.e., $ans[i] = s[i + k + 1] - s[i + 1]$.
If $k$ is a negative number, then the value at position $i$ is the sum of the values at the $|k|$ positions before position $i$, i.e., $ans[i] = s[i + n] - s[i + k + n]$.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the code
array.
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|