Break the elements Codechef Solution

We Are Discuss About CODECHEF SOLUTION

Break the elements Codechef Solution

Problem

Chef has an array A of length N. In one operation, Chef can choose any element A_i and split it into two positive integers X and Y such that X+Y = A_i.
Note that the length of array increases by 1 after every operation.

Determine the minimum numbers of operations required by Chef to make parity of all the elements same.

It is guaranteed that parity of all the elements can be made equal after applying the above operation zero or more times.

Input Format

• The first line of input will contain a single integer T, denoting the number of test cases.
• Each test case consists of multiple lines of input.
• The first line of each test case contains a single integer N — the length of array A.
• Next line contains N space-separated integers A_1, A_2, A_3, \dots, A_N – denoting the array A.

Output Format

For each test case, output the minimum number of operations required to make parity of all elements same.

Constraints

• 1 \leq T \leq 4000
• 1 \leq N \leq 10^5
• 1 \leq A_i \leq 10^9
• Sum of N does not exceed 2 \cdot 10^5

Sample 1:

Input

Output

2
4
1 3 5 7
3
1 2 3

0
1


Explanation:

Test case 1: All the elements have the same parity since all are odd. Thus, we need zero operations.

Test case 2: In one operation, we can split the element A_2 = 2 to X = 1 and Y = 1 such that X+Y = 2. Thus, the array now becomes A = [1, 1, 1, 3]. All the elements have the same parity since all are odd. Thus, we need only one operation.

Break the elements Codechef Solution

Yhaa You have done it but next? if YOU Want to Get Others Please Visit Here JOIN NOW