# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Utkarsh Gupta

Tester: Satyam, Tejas Pandey

Editorialist: Pratiyush Mishra

# DIFFICULTY:

1191

# PREREQUISITES:

None

# 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.

# EXPLANATION:

Observation \;1: We can convert an even number, say x to two odd numbers by splitting into 1 and x-1 but we cannot convert an odd number to two even numbers.

Thus if there is any odd number present in the array we will have to make parity of each element in the array as odd.

Therefore there can be two cases:

Case \; 1: All elements are even

In this case answer would be 0, since parity of each element is same, that is even.

Case \; 2: All elements are not even:

In this case, we will calculate number of even elements and our answer would be the number of even elements since we will apply operation on each even element to split it into two odd elements.

# TIME COMPLEXITY:

O(N), for each test case.

# SOLUTION:

Editorialistâ€™s Solution

Setterâ€™s Solution

Tester1â€™s Solution

Tester2â€™s Solution