Given an array of N integers, you have to minimize the number of integers in final array after performing the following operation any number of times (including zero).
Select any two integers, such that their sum is even, remove both of them from array and insert their sum into array.
- Minimum number of elements in final array will always be 1 or 2.
- Sum of two numbers of same parity is even.
Which means that our operation will always be applied on two odd or two even numbers, but never on one odd and one even number.
- This problem can be solved even using two booleans, without storing the elements, though it isn’t necessary to solve the problem. Frequency of odd and even number serve the purpose.
Operation can only be applied on elements with same parity because sum of two number with different parity is always odd, thus, not allowed by our operation.
Minimum number of elements in final array will always be 1 or 2.
Suppose our final array contains more than two, say 3 elements. Then, either the frequency of either odd or even elements will be greater than one, Thus, allowing us to perform one more operation, thereby reducing the size of final array to 2.
Size of final array will be 1, if given array contains even number of odd elements, thus no odd number in final array.
For all even numbers, we can just merge them all into a single number. If there are M odd numbers in given array, we can merge floor(M/2) pair of odd numbers, resulting in one even number and one odd number (only if M is odd).
Thus, there will be one odd number (if frequency of odd numbers in array is odd), and/or one even number (if given array has at least one even number or at least two odd numbers).
We can separately determine if the final array will contain odd element and/or even element and output accordingly.
Time Complexity is O(N). Space Complexity is O(1).