Morgan Stanley OA-8 2022

Problem Description

You are given an array of size n. You need to remove elements from the array in such a way that exactly three adjacent elements are removed in one turn. The elements that can be removed must satisfy the following conditions:

• The second element is k greater than the first element.
• The third element is k greater than the second element.

The goal is to continue removing such triplets until no further triplets can be removed, and return the size of the smallest possible array.

Note: If the array becomes empty after removing all possible triplets, return -1.

Input Format:

• The first line contains two integers n and k, where:
  • n is the size of the array.
  • k is the difference required between consecutive elements in the triplet.
• The second line contains n integers representing the elements of the array.

Output Format:

• Return the size of the smallest possible array after removing all possible triplets. If the array becomes empty, return -1.

Constraints:

• 1 <= n <= 1000
• 1 <= arr[i] <= 10^9

Sample Input 1:

10 2
2 4 6 8 10 12 8 10 6 8

Sample Output 1:

1

Sample Input 2:

6 1
12 13 14 15 16 19

Sample Output 2:

3

Explanation:

1. In the first example:
   • You can remove [2, 4, 6], [8, 10, 12], and [6, 8, 10], reducing the array to size 1.
2. In the second example:
   • There are no valid triplets that satisfy the conditions. Hence, the array size remains 3.