JP Morgan OA 2022 - Size of Smallest Possible Array

Implement the following function:

int MinSizeArray(int* arr, int n, int k);

The function accepts a positive integer array arr consisting of n elements and a positive integer k as its argument.

Remove the elements of the array according to the following rules:

1. Exactly three elements are removed in one turn.
2. The removed three elements must be adjacent in the array, i.e., arr[i], arr[i+1], arr[i+2].
3. The second element must be k greater than the first element, and the third element must be k greater than the second element, i.e.,
   [ arr[i+1] - arr[i] = k ]
   [ arr[i+2] - arr[i+1] = k ]

Implement the function to remove elements from the array until no further triplets can be removed and return the size of the smallest possible such array.

Note:
Return -1 if arr is empty.

Example:

Input:

k: 2
arr: [2, 4, 6, 8, 10, 12, 8, 10, 6, 8]

Output:

1

Explanation:
One way of removing elements from the array is:

1. Elements (8, 10, 12) at positions (3, 4, 5) are removed to get the array
   [2, 4, 6, 8, 10, 6, 8].
2. Then, elements (6, 8, 10) at positions (2, 3, 4) are removed to get the array
   [2, 4, 6, 8].
3. Then, elements (2, 4, 6) at positions (0, 1, 2) are removed to get the array
   [8].

Size of the final array is 1. Thus, the output is 1.

Custom Input Format for the Above Case:

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

(The first line represents 'k', the second line represents 'n', the third line represents the elements of the array 'arr'.)

Sample Input:

k: 1
arr: [12, 13, 14, 15, 16, 19]

Sample Output:

3