• Leetcode POTDs

Problem 1652 Defuse the Bomb

Problem Statement

Link - Problem 1652

Question

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 the ith number with the sum of the next k numbers.
• If k < 0, replace the ith number with the sum of the previous k numbers.
• If k == 0, replace the ith 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.

Constraints:

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

Solution

class Solution {
public:
    vector<int> decrypt(vector<int>& code, int k) {
        vector<int> result(code.size(), 0);
        if (k == 0)
            return result;

        int start = 1, end = k, sum = 0;
        if (k < 0) {
            start = code.size() - abs(k);
            end = code.size() - 1;
        }

        for (int i = start; i <= end; i++)
            sum += code[i];

        for (int i = 0; i < code.size(); i++) {
            result[i] = sum;
            sum -= code[start % code.size()];
            sum += code[(end + 1) % code.size()];
            start++;
            end++;
        }
        return result;
    }
};

Complexity Analysis

| Algorithm     | Time Complexity | Space Complexity |
| ------------- | --------------- | ---------------- |
| SlidingWindow | O(n)            | O(n)             |

Explanation

1. Intuition

- The problem requires us to decrypt a circular array by replacing each number with the sum of the next k numbers.
- If k is 0, all numbers are replaced with 0.
- If k is negative, we need to sum the previous k numbers.
- We can use a sliding window approach to calculate the sum of k numbers.
- We need to handle the circular nature of the array by using the modulus operator.

2. Implementation

• We first check if k is 0, in which case we return an array of zeros.
• We initialize the start and end indices of the sliding window based on the value of k.
• We calculate the sum of the first k numbers using a for loop.
• We then iterate over the array, replacing each number with the sum of the k numbers.
• We update the sum by subtracting the number that just left the window and adding the number that just entered the window.
• We use the modulus operator to handle the circular nature of the array.
• The code snippet sum -= code[start % code.size()]; sum += code[(end + 1) % code.size()]; updates the sum for the next iteration.
• The code snippet start++; end++; moves the sliding window to the next position.

Complexity Analysis

Time Complexity:

• The outer loop in the solution iterates over each element in the code vector once.
• Inside the loop, a constant number of operations are performed, namely addition, subtraction, and assignment, for each element in the code vector.
• There are no nested loops in the solution, thus time complexity doesn’t compound with more iterations.

Space Complexity:

• The solution uses a new vector of the same size as the input code vector to store the result.
• No additional space is used that scales with the input size, except for a constant amount of space to store the variables start, end, and sum.