Arrays: Find the minimum number to an array so the sum becomes even

Problem Statement:

You are given an array, you need to find the minimum number, that is greater than 0, to the array that the sum of the array become even.

Example:

Input : 1 2 3 4 5 6 7 8
Output : 2

The sum of the array is 36, so the minimum number to be added is 2.

Solution Explanation:

The solution is very simple, we will calculate the number of odd numbers of elements in the array.

If the count of add number is even then return 2, else return 1.

In out example [1 2 3 4 5 6 7 8], the odd number count is 4.

We know the sum of even numbers of odd number is even. Hence it will need to add 2.

Time Complexity: O(n)
Space Complexity: O(1)

Code Solution

#include <iostream> 
using namespace std; 

int solution(int arr[], int n) 
{ 
	// count the number of odd numbers
	int odd = 0; 
	for (int i = 0; i < n; i++) 
		if (arr[i] % 2) 
			odd += 1; 
	
return (odd % 2)? 1 : 2; 
} 

int main() 
{ 
	int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 
	int n = sizeof(arr) / sizeof(arr[0]); 

	cout << solution(arr, n); 

	return 0; 
} 

Output

1