Given an array Arr[] of N integers. The task is to find the minimum number of elements needed to be removed from the array so that the sum of the remaining elements is odd. Considering there is at least one odd number.
Examples:
Input: arr[] = {1, 2, 3, 4}
Output: 1
Remove 1 to make array sum odd.
Input: arr[] = {4, 2, 3, 4}
Output: 0
Sum is already odd.
Approach: The idea to solve this problem is to first recall the below properties of ODDs and EVENs:
- odd + odd = even
- odd + even = odd
- even + even = even
- odd * even = even
- even * even = even
- odd * odd = odd
As the sum of any number of even numbers is even. So the count of even doesn’t matter.
And the sum of the odd numbers of an odd number is always odd. So to make the array sum odd, the count of odd numbers must be odd.
So, count the number of odd numbers and check if the count is odd then no removals required. Else the count is even then 1 odd number needs to be removed.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <iostream>using namespace std;// Function to find minimum removalsint findCount(int arr[], int n){ // Count odd numbers int countOdd = 0; for (int i = 0; i < n; i++) if (arr[i] % 2 == 1) countOdd++; // If the counter is odd return 0 // otherwise return 1 if (countOdd % 2 == 0) return 1; else return 0;}// Driver Codeint main(){ int arr[] = { 1, 2, 3, 5, 1 }; int n = sizeof(arr) / sizeof(arr[0]); cout << findCount(arr, n); return 0;} |
Java
// Java implementation of the above approach class GfG { // Function to find minimum removals static int findCount(int arr[], int n) { // Count odd numbers int countOdd = 0; for (int i = 0; i < n; i++) if (arr[i] % 2 == 1) countOdd++; // If the counter is odd return 0 // otherwise return 1 if (countOdd % 2 == 0) return 1; else return 0; } // Driver Code public static void main(String[] args) { int arr[] = { 1, 2, 3, 5, 1 }; int n = arr.length; System.out.println(findCount(arr, n)); }} // This code is contributed by// Prerna Saini |
Python3
# Python3 implementation of the # above approach # Function to find minimum removals def findCount(arr, n) : # Count odd numbers countOdd = 0; for i in range(n) : if (arr[i] % 2 == 1) : countOdd += 1; # If the counter is odd return 0 # otherwise return 1 if (countOdd % 2 == 0) : return 1; else : return 0; # Driver Code if __name__ == "__main__" : arr = [ 1, 2, 3, 5, 1 ]; n = len(arr) ; print(findCount(arr, n)); # This code is contributed by Ryuga |
C#
// C# implementation of the approach using System;class GfG { // Function to find minimum removals static int findCount(int []arr, int n) { // Count odd numbers int countOdd = 0; for (int i = 0; i < n; i++) if (arr[i] % 2 == 1) countOdd++; // If the counter is odd return 0 // otherwise return 1 if (countOdd % 2 == 0) return 1; else return 0; } // Driver Code public static void Main(String[] args) { int []arr = { 1, 2, 3, 5, 1 }; int n = arr.Length; Console.WriteLine(findCount(arr, n)); }}// This code has been contributed by 29AjayKumar |
PHP
<?php// PHP implementation of the above approach // Function to find minimum removals function findCount($arr, $n) { // Count odd numbers $countOdd = 0; for ($i = 0; $i < $n; $i++) if ($arr[$i] % 2 == 1) $countOdd++; // If the counter is odd return 0 // otherwise return 1 if ($countOdd % 2 == 0) return 1; else return 0; } // Driver Code $arr = array(1, 2, 3, 5, 1); $n = sizeof($arr);echo(findCount($arr, $n)); // This code is contributed by// Code_Mech.?> |
Javascript
<script>// Javascript implementation of the above approach// Function to find minimum removalsfunction findCount(arr, n){ // Count odd numbers var countOdd = 0; for (var i = 0; i < n; i++) if (arr[i] % 2 == 1) countOdd++; // If the counter is odd return 0 // otherwise return 1 if (countOdd % 2 == 0) return 1; else return 0;}// Driver Codevar arr = [ 1, 2, 3, 5, 1 ];var n = arr.length;document.write( findCount(arr, n));</script> |
Output:
1
Time Complexity: O(n), where n is the size of the array.
Auxiliary Space: O(1), no extra space required so it is a constant.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
