Introduction

You have a bomb to defuse, and your time is running out! Your informer has provided you with a circular array code of length n and a key k. To decrypt the code, you must replace every number. All the numbers are replaced simultaneously according to the following rules:

• 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, your task is to return the decrypted code to defuse the bomb!

Problem Statement

You are given a circular array code of length n and an integer key k. You need to return the decrypted code.

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]

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.

Different Approaches

1 Sliding Window

Algorithm:

1. Initialize an empty vector decrypted_code to store the decrypted code.
2. Iterate through each element of the circular array code.
   1. If k > 0, calculate the sum of the next k numbers.
   2. If k < 0, calculate the sum of the previous k numbers.
   3. If k == 0, replace the current number with 0.
3. Return the decrypted_code.

Code Implementation in C++:

#include <iostream>
#include <vector>

using namespace std;

vector<int> decrypt(vector<int>& code, int k) {
    int n = code.size();
    vector<int> decrypted_code(n, 0);
    
    if (k == 0) return decrypted_code; // If k is 0, replace all numbers with 0
    
    for (int i = 0; i < n; i++) {
        int sum = 0;
        if (k > 0) { // If k > 0, replace the ith number with the sum of the next k numbers
            for (int j = 1; j <= k; j++) {
                sum += code[(i + j) % n];
            }
        } else { // If k < 0, replace the ith number with the sum of the previous k numbers
            for (int j = -1; j >= k; j--) {
                sum += code[(i + j + n) % n];
            }
        }
        decrypted_code[i] = sum;
    }
    
    return decrypted_code;
}

int main() {
    vector<int> code = {5, 7, 1, 4};
    int k = 3;
    vector<int> decrypted_code = decrypt(code, k);

    cout << "Decrypted code: ";
    for (int num : decrypted_code) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Explanation:

Consider the example code = [5, 7, 1, 4] and k = 3.

Initial Variables:

• code = [5, 7, 1, 4]
• k = 3

Step 1: Initialize an empty vector decrypted_code to store the decrypted code.

decrypted_code = []

Step 2: Iterate through each element of the circular array code.

For each element code[i], calculate the sum of the next k numbers.

• i = 0
  • Calculate the sum of the next 3 numbers: sum = code[(0+1) % 4] + code[(0 + 2) % 4] + code[(0 + 3) % 4]
  • The % modulus operator to handle the circular nature of the array.
    This ensures that when we reach the end of the array, we wrap around the beginning.
  • sum = code[1] + code[2] + code[3] = 7 + 1 + 4 = 12
  • Add the sum to decrypted_code:
    • decrypted_code.push_back(12)
• i = 1
  • Calculate the sum of the next 3 numbers: sum = code[(1 + 1) % 4] + code[(1 + 2) % 4] + code[(1 + 3) % 4]
  • sum = code[2] + code[3] + code[0] = 1 + 4 + 5 = 10
  • Add the sum to decrypted_code:
    • decrypted_code.push_back(10)
• i = 2
  • Calculate the sum of the next 3 numbers: sum = code[(2 + 1) % 4] + code[(2 + 2) % 4] + code[(2 + 3) % 4]
  • sum = code[3] + code[0] + code[1] = 4 + 5 + 7 = 16
  • Add the sum to decrypted_code:
    • decrypted_code.push_back(16)
• i = 3
  • Calculate the sum of the next 3 numbers: sum = code[(3 + 1) % 4] + code[(3 + 2) % 4] + code[(3 + 3) % 4]
  • sum = code[0] + code[1] + code[2] = 5 + 7 + 1 = 13
  • Add the sum to decrypted_code:
    • decrypted_code.push_back(13)

Complexity Analysis:

Time Complexity: O(n*k)

• Iterating through each element of the circular array takes O(n) time, where n is the length of the array.
• Calculating the sum of the next k or previous k numbers for each element takes O(k) time.
• Therefore, the overall time complexity is O(n * k).

Space Complexity:O(n)

• We use an additional vector decrypted_code of size n to store the decrypted code, which requires O(n) space.
• Apart from this, we use a constant amount of extra space.
• Therefore, the overall space complexity is O(n).