algoadvance

Leetcode 1652. Defuse the Bomb

Problem Statement

You have a bomb to defuse, and your time is running out! Your task is to find the code to defuse the bomb by following the instructions below:

• You have a code represented by a circular array code of length n.
• A certain key is required to defuse the bomb, where key determines the behavior of the array transformation.

You need to transform the array by creating a new array answer of the same length where answer[i] is the sum of the next k elements (to the right if k is positive, to the left if k is negative) in the circular array. If k is zero, then all elements in answer should be zero.

Example

1. If the code array is [5,7,1,4] and k = 3, then the answer array should be [12,10,16,13] because:
   • For answer[0] = 7 + 1 + 4 = 12
   • For answer[1] = 1 + 4 + 5 = 10 (wrap around)
   • For answer[2] = 4 + 5 + 7 = 16 (wrap around)
   • For answer[3] = 5 + 7 + 1 = 13 (wrap around)

Clarifying Questions

1. Can k be negative?
2. Are the values in code always integers?
3. What is the size range of the code array?
4. Is the code array guaranteed to be circular?

Let’s assume the array code contains integers and is circular, the value of k can be negative, and there are no other constraints on the values of the array elements.

Strategy

1. Initialize answer array of the same length as code with zeros.
2. Iterate through each element in the code array.
3. Depending on whether k is positive, negative, or zero:
   • If k is zero, answer[i] will be zero for all elements.
   • If k is positive, sum up the next k elements to the right, considering the circular nature of the array.
   • If k is negative, sum up the |k| elements to the left.
4. Utilize modulo operation to handle the circular nature of the array.

Code

public class Solution {
    public int[] decrypt(int[] code, int k) {
        int n = code.length;
        int[] answer = new int[n];
        
        if (k == 0) return answer;  // if k is 0, return array of all zeros
        
        for (int i = 0; i < n; i++) {
            int sum = 0;
            if (k > 0) {
                // Sum next k elements to the right
                for (int j = 1; j <= k; j++) {
                    sum += code[(i + j) % n];
                }
            } else {
                // Sum |k| elements to the left
                for (int j = 1; j <= -k; j++) {
                    sum += code[(i - j + n) % n];
                }
            }
            answer[i] = sum;
        }
        
        return answer;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] code = {5, 7, 1, 4};
        int k = 3;
        int[] result = sol.decrypt(code, k);
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}

Time Complexity

• The overall time complexity of this solution is O(n *

  k

  ). This is because for each element in code, we are potentially summing up to |k| elements, where n is the length of the code array and |k| is the absolute value of k.

• Space complexity is O(n) for the answer array.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?