Question

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 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

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 position i is the sum of the values at the k positions after position i, that is:

$$ ans[i] = \sum_{j=i+1}^{i+k} code[j \bmod n] $$

• 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, 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)$.

class Solution:
  def decrypt(self, code: List[int], k: int) -> List[int]:
    n = len(code)
    ans = [0] * n
    if k == 0:
      return ans
    for i in range(n):
      if k > 0:
        for j in range(i + 1, i + k + 1):
          ans[i] += code[j % n]
      else:
        for j in range(i + k, i):
          ans[i] += code[(j + n) % n]
    return ans

class Solution {
  public int[] decrypt(int[] code, int k) {
    int n = code.length;
    int[] ans = new int[n];
    if (k == 0) {
      return ans;
    }
    for (int i = 0; i < n; ++i) {
      if (k > 0) {
        for (int j = i + 1; j < i + k + 1; ++j) {
          ans[i] += code[j % n];
        }
      } else {
        for (int j = i + k; j < i; ++j) {
          ans[i] += code[(j + n) % n];
        }
      }
    }
    return ans;
  }
}

class Solution {
public:
  vector<int> decrypt(vector<int>& code, int k) {
    int n = code.size();
    vector<int> ans(n);
    if (k == 0) {
      return ans;
    }
    for (int i = 0; i < n; ++i) {
      if (k > 0) {
        for (int j = i + 1; j < i + k + 1; ++j) {
          ans[i] += code[j % n];
        }
      } else {
        for (int j = i + k; j < i; ++j) {
          ans[i] += code[(j + n) % n];
        }
      }
    }
    return ans;
  }
};

func decrypt(code []int, k int) []int {
  n := len(code)
  ans := make([]int, n)
  if k == 0 {
    return ans
  }
  for i := 0; i < n; i++ {
    if k > 0 {
      for j := i + 1; j < i+k+1; j++ {
        ans[i] += code[j%n]
      }
    } else {
      for j := i + k; j < i; j++ {
        ans[i] += code[(j+n)%n]
      }
    }
  }
  return ans
}

function decrypt(code: number[], k: number): number[] {
  const n = code.length;
  if (k === 0) {
    return code.fill(0);
  }
  const isPrefix = k < 0;
  if (isPrefix) {
    k *= -1;
  }
  const map = new Map<number, [number, number]>();
  let prefix = 0;
  let suffix = 0;
  for (let i = 1; i <= k; i++) {
    prefix += code[n - i];
    suffix += code[i];
  }
  map.set(0, [prefix, suffix]);

  for (let i = 1; i < n; i++) {
    let [p, s] = map.get(i - 1);
    p -= code[n - k - 1 + i] ?? code[i - k - 1];
    p += code[i - 1];
    s -= code[i];
    s += code[i + k] ?? code[i + k - n];
    map.set(i, [p, s]);
  }
  for (let i = 0; i < n; i++) {
    code[i] = map.get(i)[Number(!isPrefix)];
  }
  return code;
}

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.

class Solution:
  def decrypt(self, code: List[int], k: int) -> List[int]:
    n = len(code)
    ans = [0] * n
    if k == 0:
      return ans
    s = list(accumulate(code + code, initial=0))
    for i in range(n):
      if k > 0:
        ans[i] = s[i + k + 1] - s[i + 1]
      else:
        ans[i] = s[i + n] - s[i + k + n]
    return ans

class Solution {
  public int[] decrypt(int[] code, int k) {
    int n = code.length;
    int[] ans = new int[n];
    if (k == 0) {
      return ans;
    }
    int[] s = new int[n << 1 | 1];
    for (int i = 0; i < n << 1; ++i) {
      s[i + 1] = s[i] + code[i % n];
    }
    for (int i = 0; i < n; ++i) {
      if (k > 0) {
        ans[i] = s[i + k + 1] - s[i + 1];
      } else {
        ans[i] = s[i + n] - s[i + k + n];
      }
    }
    return ans;
  }
}

class Solution {
public:
  vector<int> decrypt(vector<int>& code, int k) {
    int n = code.size();
    vector<int> ans(n);
    if (k == 0) {
      return ans;
    }
    vector<int> s(n << 1 | 1);
    for (int i = 0; i < n << 1; ++i) {
      s[i + 1] = s[i] + code[i % n];
    }
    for (int i = 0; i < n; ++i) {
      if (k > 0) {
        ans[i] = s[i + k + 1] - s[i + 1];
      } else {
        ans[i] = s[i + n] - s[i + k + n];
      }
    }
    return ans;
  }
};

func decrypt(code []int, k int) []int {
  n := len(code)
  ans := make([]int, n)
  if k == 0 {
    return ans
  }
  s := make([]int, n<<1|1)
  for i := 0; i < n<<1; i++ {
    s[i+1] = s[i] + code[i%n]
  }
  for i := range code {
    if k > 0 {
      ans[i] = s[i+k+1] - s[i+1]
    } else {
      ans[i] = s[i+n] - s[i+k+n]
    }
  }
  return ans
}