Defuse the Bomb - codepath/compsci_guides GitHub Wiki

TIP102 Unit 1 Session 1 Advanced (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Easy
  • ⏰ Time to complete: 10 mins
  • 🛠️ Topics: Arrays

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Q: What is the input to the function?

    • A: The input consists of a circular array code of integers and an integer k representing the decryption key.

  • Q: What is the expected output of the function?

    • A: The function should return a new array where each element is replaced according to the rules defined by k.

  • Q: How is the replacement done?

    • A:
      • If k > 0, each element at index i is replaced by the sum of the next k elements.
      • If k < 0, each element at index i is replaced by the sum of the previous k elements.
      • If k == 0, each element is replaced by 0.

  • Q: How does the circular nature of the array affect the replacement?

    • A: The array is treated as circular, meaning the element after the last one is the first one, and the element before the first one is the last one.

  • Q: What should the function return if k == 0?

    • A: If k == 0, the function should return an array of zeros of the same length as code.

  • The function defuse() should take a circular array code and an integer k, returning a new array where each element is replaced based on the value of k.

HAPPY CASE
Input: code = [5, 7, 1, 4], k = 3
Expected Output: [12, 10, 16, 13]

Input: code = [2, 4, 9, 3], k = -2
Expected Output: [12, 5, 6, 13]

EDGE CASE
Input: code = [1, 2, 3, 4], k = 0
Expected Output: [0, 0, 0, 0]

Input: code = [5], k = 1
Expected Output: [5]

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Depending on the value of k, either sum the next k elements or the previous k elements for each element in the array. Use modulo arithmetic to handle the circular nature of the array.

1. Initialize `result` as a list of zeros with the same length as `code`.
2. If `k == 0`, return `result`.
3. Iterate through each element in `code`:
   - Initialize `sum_val` to 0.
   - If `k > 0`, sum the next `k` elements:
     - For `j` from 1 to `k`, add `code[(i + j) % n]` to `sum_val`.
   - If `k < 0`, sum the previous `k` elements:
     - For `j` from 1 to `-k`, add `code[(i - j) % n]` to `sum_val`.
   - Set `result[i]` to `sum_val`.
4. Return `result`

⚠️ Common Mistakes

  • Not handling the circular nature of the array correctly.
  • Off-by-one errors in indexing elements for summation.

I-mplement

Implement the code to solve the algorithm.

def defuse(code, k):
    n = len(code)
    result = [0] * n
    
    if k == 0:
        return result
    
    for i in range(n):
        sum_val = 0
        if k > 0:
            for j in range(1, k + 1):
                sum_val += code[(i + j) % n]
        else:
            for j in range(1, -k + 1):
                sum_val += code[(i - j) % n]
        
        result[i] = sum_val
    
    return result