Make the array even

2.5

20 votes
Bit Manipulation, Basic Programming, Basics of Bit Manipulation
Problem

You are given an array A of N integers. If you make the array whole using the following operation, then what is the minimum number of operations required to make the entire array even?

Note: It can be proved that this is always possible.

Operation

Select an index  \(1 \leq i <N\)  and perform operation:

P=Ai+Ai+1; Q=Ai-Ai+1;

Ai=P; Ai+1=Q;

Input format

  • The first line contains an integer T denoting the number of the test cases.
  • In each test case:
    • The first line contains an integer N denoting the number of elements in the array.
    • The second line contains N space-separated integers of array A.

Output format

For each test case print a single line denoting the minimum number of operations required to make the whole array even.

Constraints

  • \(1 \leq T \leq 20000\)
  • \(2 \leq N \leq 200000\)
  • \(1 \leq A_i \leq 1e9 \forall i \in [1,N]\)
  • Sum of N over all test cases will not exceed 200000
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

If we choose index 1 A1=1+3=4 and A2=1-3=-2.

So only one operation is required to make array even.

Editor Image

?