Jump to Sibling Solution | CodeChef Problem Solution 2022

Jump to Sibling Solution | CodeChef Problem Solution 2022

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

While standing at the ith$i^{th}$ index (1≤i<N)$(1\le i<N)$ of the array, Chef can perform the following types of jumps:

• 𝙹𝚞𝚖𝚙 𝟷$\mathtt{\text{Jump 1}}$: Jump to the immediate next index j$j$ such that Ai$A_i$ and Aj$A_j$ have the same parity.
• 𝙹𝚞𝚖𝚙 𝟸$\mathtt{\text{Jump 2}}$: Jump to the immediate next index j$j$ such that Ai$A_i$ and Aj$A_j$ have different parity.

Given that Chef can perform 𝙹𝚞𝚖𝚙 𝟸$\mathtt{\text{Jump 2}}$ at most once, Lav wants to find the minimum number of jumps required by the Chef to reach the last index of the array.

Input Format

• First line will contain T$T$, the number of test cases. Then the test cases follow.
• The first line of each test case contains a single integer N$N$ - the size of the array A$A$.
• The second line of each test case contains N$N$ integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$ - the elements of the array A$A$.

Output Format

For each test case, output the minimum number of jumps required by the Chef to reach the last index of the array.

Constraints

• 1≤T≤100$1\le T\le 100$
• 2≤N≤104$2\le N\le {10}^4$
• 1≤Ai≤109$1\le A_i\le {10}^9$

Sample Input 1 

2
4
1 2 3 4
4
2 1 3 4

Sample Output 1 

2
1

Explanation

Test Case 1$1$: The minimum number of jumps required by the Chef to reach the last index is 2$2$. Chef is initially standing at index 1$1$.

• Chef chooses 𝙹𝚞𝚖𝚙 𝟸$\mathtt{\text{Jump 2}}$ and jumps to index 2$2$ as it is the immediate next element with different parity.
• Chef chooses 𝙹𝚞𝚖𝚙 𝟷$\mathtt{\text{Jump 1}}$ and jumps to index 4$4$ as it is the immediate next element with the same parity.

Test Case 2$2$: The minimum number of jumps required by the Chef to reach the last index is 1$1$. Chef is currently standing at index 1$1$.

• Chef chooses 𝙹𝚞𝚖𝚙 𝟷$\mathtt{\text{Jump 1}}$ and jumps to index 4$4$ as it is the immediate next element with the same parity.