Minimum array size after repeated replacement of even sum pair with sum
Given an array of size N. Choose a random pair of elements from the sequence such that their sum is even, delete those two elements from the sequence and insert their sum into the sequence instead in order to minimize the length of the array. Finally, print the minimum possible size of the array.
Examples :
Input : 88 98 1 7 3 Output : 2 By following above rules --[88, 98, 1, 10] [98, 88, 1]---[186, 1]--we cannot move further since 186 + 1 = 187, which is not even. So, size = 2. Input : 7 4 3 2 6 Output : 1 delete 7 and 3, insert 10---[10, 4, 2, 6] repeating the process of deleting and inserting---[14, 8]--[22] size of array becomes 1.
Approach: A pair of numbers can sum upto an even number if both the numbers are even or both of them are odd. So, we just need to count the odd numbers present in the given array. Answer can either be 2 or 1 (and nothing else), depending upon the condition. If total number of odds in the array is an odd number then print 2 otherwise print 1.
Implementation:
C++
// CPP Program to find minimum size of array // after repeatedly replacing even sum pair // with the sum #include <bits/stdc++.h> using namespace std; // function to count and check // total number of odds bool check( int a[], int n) { int i, c = 0; // loop to count total no. of // odd numbers in the array if (n == 1) return false ; for (i = 0; i < n; i++) if (a[i] & 1) c++; if (c & 1) return true ; return false ; } // Driver program to test // above function int main() { int n, a[] = { 7, 4, 3, 2, 6 }; n = sizeof (a) / sizeof (a[0]); // if in total there are // odd number of odds if (check(a, n)) cout << 2; else cout << 1; return 0; } |
Java
// Java Program to find minimum size of array // after repeatedly replacing even sum pair // with the sum import java.io.*; import java.math.*; class GFG { // function to count and check // total number of odds static boolean check( int a[], int n) { int i, c = 0 ; // loop to count total no. of // odd numbers in the array if (n == 1 ) return false ; for (i = 0 ; i < n; i++) if ((a[i] & 1 )== 1 ) c++; if ((c & 1 ) == 1 ) return true ; return false ; } // Driver program to test // above function public static void main(String args[]) { int n, a[] = { 7 , 4 , 3 , 2 , 6 }; n = a.length; // if in total there are // odd number of odds if (check(a, n)) System.out.println( "2" ); else System.out.println( "1" ); } } // This code is contributed by Nikita Tiwari. |
Python 3
# Python 3 Program to illustrate # the above approach # function to count and check # total number of odds def check(a): c = 0 # if length is 1, then we return # false in order to get output 1 if len (a) = = 1 : return False # loop to count number of odds for i in a: if i & 1 : c + = 1 # if c is odd if c & 1 : return True return False # Driver program to test above function a = [ 7 , 4 , 3 , 2 , 6 ] # if in total there are odd # number of odd numbers if (check(a)): print ( 2 ) else : print ( 1 ) |
C#
// C# Program to find minimum size of array // after repeatedly replacing even sum pair // with the sum using System; class GFG { // function to count and check // total number of odds static bool check( int []a, int n) { int i, c = 0; // loop to count total no. of // odd numbers in the array if (n == 1) return false ; for (i = 0; i < n; i++) if ((a[i] & 1)==1) c++; if ((c & 1) == 1) return true ; return false ; } // Driver program public static void Main() { int n; int []a = { 7, 4, 3, 2, 6 }; n = a.Length; // if in total there are // odd number of odds if (check(a, n)) Console.WriteLine( "2" ); else Console.WriteLine( "1" ); } } // This code is contributed by vt_m. |
PHP
<?php // PHP Program to find // minimum size of array // after repeatedly replacing // even sum pair with the sum // function to count and check // total number of odds function check( $a , $n ) { $i ; $c = 0; // loop to count total // no. of odd numbers // in the array if ( $n == 1) return false; for ( $i = 0; $i < $n ; $i ++) if ( $a [ $i ] & 1) $c ++; if ( $c & 1) return true; return false; } // Driver Code $n ; $a = array ( 7, 4, 3, 2, 6 ); $n = count ( $a ); // if in total there are // odd number of odds if (check( $a , $n )) echo 2; else echo 1; // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript Program to find minimum size of array // after repeatedly replacing even sum pair // with the sum // function to count and check // total number of odds function check(a, n) { let i, c = 0; // loop to count total no. of // odd numbers in the array if (n == 1) return false ; for (i = 0; i < n; i++) if ((a[i] & 1)==1) c++; if ((c & 1) == 1) return true ; return false ; } let n; let a = [7, 4, 3, 2, 6]; n = a.length; // if in total there are // odd number of odds if (check(a, n)) document.write( "2" + "</br>" ); else document.write( "1" ); // This code is contributed by divyeshrabadiya07. </script> |
Output
1
Time Complexity: O(n)
Space Complexity: O(1).