Defuse the Bomb

easy sliding window circular array

Problem

A bomb's code is a circular array of n digits plus a key k. To decrypt it, every position is replaced simultaneously: if k > 0, position i becomes the sum of the next k numbers; if k < 0, it becomes the sum of the previous |k| numbers; if k = 0, it becomes 0. Because the array is circular, sums wrap around either end.

Constraints: 1 ≤ n ≤ 100, 1 ≤ code[i] ≤ 100, and −(n − 1) ≤ k ≤ n − 1. Return the decrypted array.

Inputcode = [5,7,1,4], k = 3

Output[12,10,16,13]

Each digit becomes the sum of the next 3, wrapping around: 7+1+4=12, 1+4+5=10, 4+5+7=16, 5+7+1=13.

code (comma-separated, max 12)

def decrypt(code, k):
    n = len(code)
    res = [0] * n
    if k == 0:
        return res
    lo, hi = (1, k) if k > 0 else (n + k, n - 1)
    win = sum(code[j % n] for j in range(lo, hi + 1))
    for i in range(n):
        res[i] = win
        win -= code[lo % n]
        win += code[(hi + 1) % n]
        lo += 1
        hi += 1
    return res

function decrypt(code, k) {
  const n = code.length;
  const res = new Array(n).fill(0);
  if (k === 0) return res;
  let lo = k > 0 ? 1 : n + k;
  let hi = k > 0 ? k : n - 1;
  let win = 0;
  for (let j = lo; j <= hi; j++) win += code[j % n];
  for (let i = 0; i < n; i++) {
    res[i] = win;
    win -= code[lo % n];
    win += code[(hi + 1) % n];
    lo++; hi++;
  }
  return res;
}

int[] decrypt(int[] code, int k) {
    int n = code.length;
    int[] res = new int[n];
    if (k == 0) return res;
    int lo = k > 0 ? 1 : n + k;
    int hi = k > 0 ? k : n - 1;
    int win = 0;
    for (int j = lo; j <= hi; j++) win += code[j % n];
    for (int i = 0; i < n; i++) {
        res[i] = win;
        win -= code[lo % n];
        win += code[(hi + 1) % n];
        lo++; hi++;
    }
    return res;
}

vector<int> decrypt(vector<int>& code, int k) {
    int n = code.size();
    vector<int> res(n, 0);
    if (k == 0) return res;
    int lo = k > 0 ? 1 : n + k;
    int hi = k > 0 ? k : n - 1;
    int win = 0;
    for (int j = lo; j <= hi; j++) win += code[j % n];
    for (int i = 0; i < n; i++) {
        res[i] = win;
        win -= code[lo % n];
        win += code[(hi + 1) % n];
        lo++; hi++;
    }
    return res;
}

Explanation

The brute force recomputes a fresh sum of |k| values for each of the n positions, costing O(n·k). The sliding window insight is that the windows for two neighbouring positions overlap almost completely: moving from index i to i + 1 shifts the whole window right by one, so exactly one value leaves on the left and one value enters on the right. Keeping a running sum makes each move O(1).

Circularity is handled with modulo arithmetic: every read is code[j % n]. We track the window with two raw pointers lo and hi that only ever grow; taking them mod n at read time wraps them back into the array, so we never have to special-case the seam.

The only real decision is where the first window sits. For k > 0, position 0 needs the next k values, indices 1..k. For k < 0 it needs the previous |k| values, which (wrapping backwards from 0) are indices n+k..n−1. If k = 0 there is no window at all and the answer is simply all zeros.

Walking through the default example, code = [5,7,1,4] and k = 3: the first window covers indices 1..3, sum 7+1+4 = 12, so res[0] = 12. Slide: drop code[1] = 7, add code[0] = 5 → 10 = res[1]. Drop code[2] = 1, add code[1] = 7 → 16 = res[2]. Drop code[3] = 4, add code[2] = 1 → 13 = res[3]. The decrypted code is [12,10,16,13].

Building the initial sum costs O(|k|) ≤ O(n), and the loop then does n iterations of constant work, so the whole decryption runs in O(n) time. Beyond the required output array the algorithm keeps only the two pointers and one running sum, so extra space is O(1) and total space is O(n).

Time: O(n) Space: O(n)