AlgoUniversity
  • Go Back
Discussion
Smallest Size Of Array :

Author

Akash

Difficulty Level : Hard

Submissions : 219

Asked In : JP-Morgan

Marks :10

: 8 | : 0

Given a $$$n$$$ sized array, remove the elements of the array according to the following rules:

Exactly three elements are removed in one turn.

The removed three elements must be adjacent in the array, i.e., $$$arr[j]$$$, $$$arr[j+1]$$$, and $$$arr[j+2]$$$. And 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[j+1]-arr[j]=k$$$ and $$$arr[j+2]-arr[j+1]=k$$$.

Remove the 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 the array is empty.

Input

The first line contains two integers $$$n$$$ and $$$k$$$, $$$(1 \le n \le 10^3)$$$, the size of the array and the difference $$$k$$$.

The second line contains n integers, $$$(1 \le arr_i \le 10^9)$$$

Output

Return the size of the smallest possible such array.

Examples

Input
10 2
2 4 6 8 10 12 8 10 6 8
Output
1
Input
6 1
12 13 14 15 16 19
Output
3

You need to login to view your submissions.

You need to login to view all submissions.

Loading...

Result : Executed

Loading...

Feel something is wrong with the test cases?

Result : Accepted

Test Cases :

You need to Log In
We're glad that you want to attempt this problem!

But to Run or Submit the Problem, you need to Log In.

Continue to Log In
Challenge Submitted!

Your challenge has been submitted successfully.

You will get a response soon via WhatsApp or Email.

Challenge
Facing issue while trying to solve the problem! Don't worry, we got you covered!

Do let us know your issue.

Looks good!
Please enter your issue / feedback.

How do we get in touch with you?
Looks good!
Please enter your phone no.
Looks good!
Please enter your email address.