Minimum elements to be removed from array to make the sum even

Given an array of integer and you have to find minimum no of integers or elements from array need to be removed so that sum of all elements of array results an even value.

The first thing which comes in mind is that sum can be even only if number of odd terms are even. If number of odd terms are odd sum will result in odd value.
As we know -

odd+odd = even
even+odd = odd
--> even times odd = even
--> odd times odd = odd

No issue with number of even values in array either they are odd times or even times their sum will always result in even value.

for example.

arr = [1,2,3,4,5]
even elements - 2,4
odd elements - 1,3,5
no of odd elements = 3
sum of odd elements = 1+3+5 = 9 --> odd 
sum of even elements = 2+4 = 8 --> even
odd + even = odd

It was clear from the observation(i.e no of odd elements is odd) that sum will result in odd.

Then to make the sum even what changes we can do here?
Which type of elements we need to remove?
Think for a while, you will get the answer if you have got the above logics.

Okay, So if sum is odd we need to delete one element having odd value.
As sum is odd and removing odd value will result in even sum.
i.e sum ---> odd
element ---> odd
sum = sum-element
sum = odd - odd ---> even
i.e arrli = [1,2,3,4,5]
sum = 1+2+3+4+5 = 15
if we remove any one of the odd elements i.e
15-1 = 14
15-3 = 12
15-5 = 10
all will results in even value of sum.

So overall conclusion is -
i) If sum is odd, it means number of odd terms are odd.
So remove one odd element to make count of odd element even in an array.
--> minimum no of removals = 1.
ii) If sum is even, it means number of odd terms are even.
--> minimum no of removals = 0, or no need to remove.

Algorithm

1. Traverse an array and count the no of odd elements present in it.
2. If number of odd elements is odd return 1 else return 0.

Implementation

import java.util.* ;
public class OpenGenus {
    //method to find number of elements needed to remove to make sum even.
    //count number of odd elements in array.
    public static int CountRemoves(int arr[], int N)
    {
        int CountOdd = 0;

        for (int i = 0; i &lt N; i++)
            if (arr[i] % 2 == 1)

                /* count number of odd elements */
                CountOdd++;

        /* if count of odd elements is even return 0
        else return 1 */
        if (CountOdd % 2 == 0)
            return 0;
        else
            return 1;
    }

    // Driver method

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        // Input size of array
        System.out.println("Enter the size of array");
        int N = sc.nextInt();
        // Input array
        System.out.println("Input the array");
        int[] arr = new int[N];
        for(int i=0; i<N; i++){
            arr[i] = sc.nextInt();
        }
        // call CountRemoves method and print the result.
        System.out.println("Number of elements need to be removed is"+" "+ CountRemoves(arr, N));
    }
}

See some of inputs and their respective outputs.

Enter the size of array
4
Input the array
2 4 6 8
Number of elements need to be removed is 0

Enter the size of array
10
Input the array
3 5 7 8 15 21 52 63 93 12
Number of elements need to be removed is 1

Complexity

• Time-complexity : O(N) where N is length of array, as we are traversing an array in one for loop.
• Space-complexity : O(1), as no extra space taken.