# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Neerav

Tester: Felipe Mota, Abhinav Sharma

Editorialist: Pratiyush Mishra

# DIFFICULTY:

1888

# PREREQUISITES:

None

# PROBLEM:

Lav has an array A of size N. He noticed that Chef is initially standing at the **first** index of the array.

While standing at the i^{th} index (1β€i<N) of the array, Chef can perform the following types of jumps:

- πΉπππ π·: Jump to the immediate next index j such that Ai and Aj have the
**same**parity. - πΉπππ πΈ: Jump to the immediate next index j such that Ai and Aj have
**different**parity.

Given that Chef can perform πΉπππ πΈ **at most once**, Lav wants to find the **minimum** number of jumps required by the Chef to reach the **last** index of the array.

# EXPLANATION:

For each test case, the input consists of an array of size N.

Two cases are possible for this particular problem:

- When the first and last elements have
**same**parity. - When the first and last elements have
**different**parity.

In the first case, if we perform Jump 2 even once then it is impossible for us to reach the destination(last element). So the number of jumps will be simply **total number of elements in the array with same parity as the first element** (obviously excluding the first element).

In the second case, we have to **perform Jump 2 once** which can be done at any element having the same parity as the first element. The total number of jumps in this case will be the jumps required to reach this element plus the number of jumps to reach the last element. *This will be equivalent to the number of elements having the same parity as the first element till a particular element plus then the number of elements with different parity till the last element from here on.* So, we to have to find the **minimum value of this sum** for any element in the array having the same parity as the first element. This can be achieved using two extra arrays and pre-computing these values.

# TIME COMPLEXITY:

O(N) for each test case.

# SOLUTION:

Editorialistβs Solution

Setterβs Solution

Tester-1βs Solution

Tester-2βs Solution