You are working in the Data Consistency team of your company. You are allocated a task as follows:

• You have a data stream consisting of an equal number of odd and even numbers. You can make separations in the data stream but the number of odd elements should be equal to the number of even elements in both partitions after separation. Also, if you make a separation between a number x and number y, then the cost of this operation will be |x-y| coins.

You are given the following:

• An integer N
• An array arr
• An integer K

Task

Determine the maximum number of separations that can be made in the array by spending no more than K coins.

Example

Assumptions

• N = 6
• K = 4
• arr = [1, 2, 5, 10, 5, 20]

Approach

• The optimal answer is to split-sequence between 2 and 5. The price of this cut is equal to 3 coins, hence answer is 1.

Function description

Complete the function Decryptions() which takes an integer N and an array Arr. This function takes the following parameters and returns the required answer: 

• N: Represents the size of the data stream
• K: Represents the limit of coins
• arr: Represents the data stream

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

• The first line contains the integer N.
• The second line contains integer K.
• The third line contains N integers denoting the data stream.

Output format

Print the maximum number of separations that can be made in the array by spending no more than K coins.

Constraints

  $2\leq N\leq 100$

  $1\leq K \leq100$

  $1\leq arr_i\leq 100$

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.