[Coding] Jump to Sibling solution codechef

Jump to Sibling solution codechef

 

Lav has an array AA of size NN. He noticed that Chef is initially standing at the first index of the array.

While standing at the ithith index (1i<N)(1≤i<N) of the array, Chef can perform the following types of jumps:

  • Jump 1Jump 1: Jump to the immediate next index jj such that AiAi and AjAj have the same parity.
  • Jump 2Jump 2: Jump to the immediate next index jj such that AiAi and AjAj have different parity.

Given that Chef can perform Jump 2Jump 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

Jump to Sibling solution codechef

  • First line will contain TT, the number of test cases. Then the test cases follow.
  • The first line of each test case contains a single integer NN – the size of the array AA.
  • The second line of each test case contains NN integers A1,A2,,ANA1,A2,…,AN – the elements of the array AA.

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

Jump to Sibling solution codechef

  • 1T1001≤T≤100
  • 2N1042≤N≤104
  • 1Ai1091≤Ai≤109

Sample Input 1 

2
4
1 2 3 4
4
2 1 3 4

Sample Output 1 

2
1

Explanation

Jump to Sibling solution codechef

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

  • Chef chooses Jump 2Jump 2 and jumps to index 22 as it is the immediate next element with different parity.
  • Chef chooses Jump 1Jump 1 and jumps to index 44 as it is the immediate next element with the same parity.

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

  • Chef chooses Jump 1Jump 1 and jumps to index 44 as it is the immediate next element with the same parity.

    ANSWER

    Click Here

Leave a Comment