Zkontrolujte, zda v poli existují dva prvky, jejichž součet se rovná součtu zbytku pole
Máme pole celých čísel a musíme v poli najít dva takové prvky, aby se součet těchto dvou prvků rovnal součtu ostatních prvků v poli.
Příklady:
Input : arr[] = {2 11 5 1 4 7} Output : Elements are 4 and 11 Note that 4 + 11 = 2 + 5 + 1 + 7 Input : arr[] = {2 4 2 1 11 15} Output : Elements do not exist A jednoduché řešení je uvažovat každý pár jeden po druhém najít jeho součet a porovnat součet se součtem ostatních prvků. Pokud najdeme pár, jehož součet je roven zbytku prvků, vypíšeme pár a vrátíme true. Časová složitost tohoto řešení je O(n 3 )
An efektivní řešení je najít součet všech prvků pole. Nechť je tento součet 'součet'. Nyní se úkol redukuje na nalezení dvojice se součtem rovným součtu/2.
Další optimalizací je, že pár může existovat pouze v případě, že součet celého pole je sudý, protože jej v podstatě rozdělujeme na dvě části se stejným součtem.
- Najděte součet celého pole. Nechť je tento součet 'součet'
- Pokud je součet lichý, vrátí hodnotu false.
- Najděte pár se součtem rovným 'součet/2' pomocí diskutované metody založené na hašování zde jako metoda 2. Pokud je pár nalezen, vytiskněte jej a vraťte hodnotu true.
- Pokud žádný pár neexistuje, vrátí false.
Níže je uvedena implementace výše uvedených kroků.
C++ // C++ program to find whether two elements exist // whose sum is equal to sum of rest of the elements. #include using namespace std ; // Function to check whether two elements exist // whose sum is equal to sum of rest of the elements. bool checkPair ( int arr [] int n ) { // Find sum of whole array int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) sum += arr [ i ]; // If sum of array is not even then we can not // divide it into two part if ( sum % 2 != 0 ) return false ; sum = sum / 2 ; // For each element arr[i] see if there is // another element with value sum - arr[i] unordered_set < int > s ; for ( int i = 0 ; i < n ; i ++ ) { int val = sum - arr [ i ]; // If element exist than return the pair if ( s . find ( val ) != s . end ()) { printf ( 'Pair elements are %d and %d n ' arr [ i ] val ); return true ; } s . insert ( arr [ i ]); } return false ; } // Driver program. int main () { int arr [] = { 2 11 5 1 4 7 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); if ( checkPair ( arr n ) == false ) printf ( 'No pair found' ); return 0 ; }
Java // Java program to find whether two elements exist // whose sum is equal to sum of rest of the elements. import java.util.* ; class GFG { // Function to check whether two elements exist // whose sum is equal to sum of rest of the elements. static boolean checkPair ( int arr [] int n ) { // Find sum of whole array int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { sum += arr [ i ] ; } // If sum of array is not even then we can not // divide it into two part if ( sum % 2 != 0 ) { return false ; } sum = sum / 2 ; // For each element arr[i] see if there is // another element with value sum - arr[i] HashSet < Integer > s = new HashSet < Integer > (); for ( int i = 0 ; i < n ; i ++ ) { int val = sum - arr [ i ] ; // If element exist than return the pair if ( s . contains ( val ) && val == ( int ) s . toArray () [ s . size () - 1 ] ) { System . out . printf ( 'Pair elements are %d and %dn' arr [ i ] val ); return true ; } s . add ( arr [ i ] ); } return false ; } // Driver program. public static void main ( String [] args ) { int arr [] = { 2 11 5 1 4 7 }; int n = arr . length ; if ( checkPair ( arr n ) == false ) { System . out . printf ( 'No pair found' ); } } } /* This code contributed by PrinciRaj1992 */
Python3 # Python3 program to find whether # two elements exist whose sum is # equal to sum of rest of the elements. # Function to check whether two # elements exist whose sum is equal # to sum of rest of the elements. def checkPair ( arr n ): s = set () sum = 0 # Find sum of whole array for i in range ( n ): sum += arr [ i ] # / If sum of array is not # even then we can not # divide it into two part if sum % 2 != 0 : return False sum = sum / 2 # For each element arr[i] see if # there is another element with # value sum - arr[i] for i in range ( n ): val = sum - arr [ i ] if arr [ i ] not in s : s . add ( arr [ i ]) # If element exist than # return the pair if val in s : print ( 'Pair elements are' arr [ i ] 'and' int ( val )) # Driver Code arr = [ 2 11 5 1 4 7 ] n = len ( arr ) if checkPair ( arr n ) == False : print ( 'No pair found' ) # This code is contributed # by Shrikant13
C# // C# program to find whether two elements exist // whose sum is equal to sum of rest of the elements. using System ; using System.Collections.Generic ; class GFG { // Function to check whether two elements exist // whose sum is equal to sum of rest of the elements. static bool checkPair ( int [] arr int n ) { // Find sum of whole array int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { sum += arr [ i ]; } // If sum of array is not even then we can not // divide it into two part if ( sum % 2 != 0 ) { return false ; } sum = sum / 2 ; // For each element arr[i] see if there is // another element with value sum - arr[i] HashSet < int > s = new HashSet < int > (); for ( int i = 0 ; i < n ; i ++ ) { int val = sum - arr [ i ]; // If element exist than return the pair if ( s . Contains ( val )) { Console . Write ( 'Pair elements are {0} and {1}n' arr [ i ] val ); return true ; } s . Add ( arr [ i ]); } return false ; } // Driver code public static void Main ( String [] args ) { int [] arr = { 2 11 5 1 4 7 }; int n = arr . Length ; if ( checkPair ( arr n ) == false ) { Console . Write ( 'No pair found' ); } } } // This code contributed by Rajput-Ji
PHP // PHP program to find whether two elements exist // whose sum is equal to sum of rest of the elements. // Function to check whether two elements exist // whose sum is equal to sum of rest of the elements. function checkPair ( & $arr $n ) { // Find sum of whole array $sum = 0 ; for ( $i = 0 ; $i < $n ; $i ++ ) $sum += $arr [ $i ]; // If sum of array is not even then we // can not divide it into two part if ( $sum % 2 != 0 ) return false ; $sum = $sum / 2 ; // For each element arr[i] see if there is // another element with value sum - arr[i] $s = array (); for ( $i = 0 ; $i < $n ; $i ++ ) { $val = $sum - $arr [ $i ]; // If element exist than return the pair if ( array_search ( $val $s )) { echo 'Pair elements are ' . $arr [ $i ] . ' and ' . $val . ' n ' ; return true ; } array_push ( $s $arr [ $i ]); } return false ; } // Driver Code $arr = array ( 2 11 5 1 4 7 ); $n = sizeof ( $arr ); if ( checkPair ( $arr $n ) == false ) echo 'No pair found' ; // This code is contributed by ita_c ?>
JavaScript < script > // Javascript program to find // whether two elements exist // whose sum is equal to sum of rest // of the elements. // Function to check whether // two elements exist // whose sum is equal to sum of // rest of the elements. function checkPair ( arr n ) { // Find sum of whole array let sum = 0 ; for ( let i = 0 ; i < n ; i ++ ) { sum += arr [ i ]; } // If sum of array is not even then we can not // divide it into two part if ( sum % 2 != 0 ) { return false ; } sum = Math . floor ( sum / 2 ); // For each element arr[i] see if there is // another element with value sum - arr[i] let s = new Set (); for ( let i = 0 ; i < n ; i ++ ) { let val = sum - arr [ i ]; // If element exist than return the pair if ( ! s . has ( arr [ i ])) { s . add ( arr [ i ]) } if ( s . has ( val ) ) { document . write ( 'Pair elements are ' + arr [ i ] + ' and ' + val + '
' ); return true ; } s . add ( arr [ i ]); } return false ; } // Driver program. let arr = [ 2 11 5 1 4 7 ]; let n = arr . length ; if ( checkPair ( arr n ) == false ) { document . write ( 'No pair found' ); } // This code is contributed by rag2127 < /script>
Výstup
Pair elements are 4 and 11
Časová složitost: Na) . unordered_set je implementován pomocí hashování. Hledání a vkládání hash časové složitosti se zde předpokládá jako O(1).
Pomocný prostor: Na)
Další efektivní přístup (optimalizace prostoru): Nejprve seřadíme pole pro Binární vyhledávání . Potom budeme iterovat celé pole a zkontrolovat, zda v poli existuje index, který se páruje s i, takže arr[index] + a[i] == Zbytkový součet pole . Binární vyhledávání můžeme použít k nalezení indexu v poli úpravou programu binárního vyhledávání. Pokud pár existuje, vytiskněte jej. jinak tisk neexistuje žádný pár.
Níže je uvedena implementace výše uvedeného přístupu:
C++ // C++ program for the above approach #include using namespace std ; // Function to Find if a index exist in array such that // arr[index] + a[i] == Rest sum of the array int binarysearch ( int arr [] int n int i int Totalsum ) { int l = 0 r = n - 1 index = -1 ; //initialize as -1 while ( l <= r ) { int mid = ( l + r ) / 2 ; int Pairsum = arr [ mid ] + arr [ i ]; //pair sum int Restsum = Totalsum - Pairsum ; //Rest sum if ( Pairsum == Restsum ) { if ( index != i ) // checking a pair has same position or not { index = mid ; } //Then update index -1 to mid // Checking for adjacent element else if ( index == i && mid > 0 && arr [ mid -1 ] == arr [ i ]) { index = mid -1 ; } //Then update index -1 to mid-1 else if ( index == i && mid < n -1 && arr [ mid + 1 ] == arr [ i ]) { index = mid + 1 ; } //Then update index-1 to mid+1 break ; } else if ( Pairsum > Restsum ) { // If pair sum is greater than rest sum our index will // be in the Range [mid+1R] l = mid + 1 ; } else { // If pair sum is smaller than rest sum our index will // be in the Range [Lmid-1] r = mid - 1 ; } } // return index=-1 if a pair not exist with arr[i] // else return index such that arr[i]+arr[index] == sum of rest of arr return index ; } // Function to check if a pair exist such their sum // equal to rest of the array or not bool checkPair ( int arr [] int n ) { int Totalsum = 0 ; sort ( arr arr + n ); //sort arr for Binary search for ( int i = 0 ; i < n ; i ++ ) { Totalsum += arr [ i ]; } //Finding total sum of the arr for ( int i = 0 ; i < n ; i ++ ) { // If index is -1 Means arr[i] can't pair with any element // else arr[i]+a[index] == sum of rest of the arr int index = binarysearch ( arr n i Totalsum ) ; if ( index != -1 ) { cout < < 'Pair elements are ' < < arr [ i ] < < ' and ' < < arr [ index ]; return true ; } } return false ; //Return false if a pair not exist } // Driver Code int main () { int arr [] = { 2 11 5 1 4 7 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); //Function call if ( checkPair ( arr n ) == false ) { cout < < 'No pair found' ; } return 0 ; } // This Approach is contributed by nikhilsainiofficial546
Java // Java program for the above approach import java.util.* ; class GFG { // Function to Find if a index exist in array such that // arr[index] + a[i] == Rest sum of the array static int binarysearch ( int arr [] int n int i int Totalsum ) { int l = 0 r = n - 1 index = - 1 ; // initialize as -1 while ( l <= r ) { int mid = ( l + r ) / 2 ; int Pairsum = arr [ mid ] + arr [ i ] ; // pair sum int Restsum = Totalsum - Pairsum ; // Rest sum if ( Pairsum == Restsum ) { if ( index != i ) // checking a pair has same // position or not { index = mid ; } // Then update index -1 to mid // Checking for adjacent element else if ( index == i && mid > 0 && arr [ mid - 1 ] == arr [ i ] ) { index = mid - 1 ; } // Then update index -1 to mid-1 else if ( index == i && mid < n - 1 && arr [ mid + 1 ] == arr [ i ] ) { index = mid + 1 ; } // Then update index-1 to mid+1 break ; } else if ( Pairsum > Restsum ) { // If pair sum is greater than rest sum // our index will be in the Range [mid+1R] l = mid + 1 ; } else { // If pair sum is smaller than rest sum // our index will be in the Range [Lmid-1] r = mid - 1 ; } } // return index=-1 if a pair not exist with arr[i] // else return index such that arr[i]+arr[index] == // sum of rest of arr return index ; } // Function to check if a pair exist such their sum // equal to rest of the array or not static boolean checkPair ( int arr [] int n ) { int Totalsum = 0 ; Arrays . sort ( arr ); // sort arr for Binary search for ( int i = 0 ; i < n ; i ++ ) { Totalsum += arr [ i ] ; } // Finding total sum of the arr for ( int i = 0 ; i < n ; i ++ ) { // If index is -1 Means arr[i] can't pair with // any element else arr[i]+a[index] == sum of // rest of the arr int index = binarysearch ( arr n i Totalsum ); if ( index != - 1 ) { System . out . println ( 'Pair elements are ' + arr [ i ] + ' and ' + arr [ index ] ); return true ; } } return false ; // Return false if a pair not exist } // Driver Code public static void main ( String [] args ) { int arr [] = { 2 11 5 1 4 7 }; int n = arr . length ; // Function call if ( checkPair ( arr n ) == false ) { System . out . println ( 'No pair found' ); } } }
Python3 # Python program for the above approach # Function to find if a index exist in array such that # arr[index] + a[i] == Rest sum of the array def binarysearch ( arr n i Totalsum ): l = 0 r = n - 1 index = - 1 # Initialize as -1 while l <= r : mid = ( l + r ) // 2 Pairsum = arr [ mid ] + arr [ i ] # Pair sum Restsum = Totalsum - Pairsum # Rest sum if Pairsum == Restsum : if index != i : # Checking if a pair has the same position or not index = mid # Then update index -1 to mid # Checking for adjacent element elif index == i and mid > 0 and arr [ mid - 1 ] == arr [ i ]: index = mid - 1 # Then update index -1 to mid-1 elif index == i and mid < n - 1 and arr [ mid + 1 ] == arr [ i ]: index = mid + 1 # Then update index-1 to mid+1 break elif Pairsum > Restsum : # If pair sum is greater than rest sum our index will # be in the Range [mid+1R] l = mid + 1 else : # If pair sum is smaller than rest sum our index will # be in the Range [Lmid-1] r = mid - 1 # Return index=-1 if a pair not exist with arr[i] # else return index such that arr[i]+arr[index] == sum of rest of arr return index # Function to check if a pair exists such that their sum # equals to rest of the array or not def checkPair ( arr n ): Totalsum = 0 arr = sorted ( arr ) # Sort arr for Binary search for i in range ( n ): Totalsum += arr [ i ] # Finding total sum of the arr for i in range ( n ): # If index is -1 means arr[i] can't pair with any element # else arr[i]+a[index] == sum of rest of the arr index = binarysearch ( arr n i Totalsum ) if index != - 1 : print ( 'Pair elements are' arr [ i ] 'and' arr [ index ]) return True return False # Return false if a pair not exist # Driver Code arr = [ 2 11 5 1 4 7 ] n = len ( arr ) # Function call if checkPair ( arr n ) == False : print ( 'No pair found' )
C# using System ; class GFG { // Function to Find if a index exist in array such that // arr[index] + a[i] == Rest sum of the array static int BinarySearch ( int [] arr int n int i int totalSum ) { int l = 0 r = n - 1 index = - 1 ; // initialize as -1 while ( l <= r ) { int mid = ( l + r ) / 2 ; int pairSum = arr [ mid ] + arr [ i ]; // pair sum int restSum = totalSum - pairSum ; // rest sum if ( pairSum == restSum ) { if ( index != i ) // checking a pair has same // position or not { index = mid ; } // Then update index -1 to mid // Checking for adjacent element else if ( index == i && mid > 0 && arr [ mid - 1 ] == arr [ i ]) { index = mid - 1 ; } // Then update index -1 to mid-1 else if ( index == i && mid < n - 1 && arr [ mid + 1 ] == arr [ i ]) { index = mid + 1 ; } // Then update index-1 to mid+1 break ; } else if ( pairSum > restSum ) { // If pair sum is greater than rest sum // our index will be in the Range [mid+1R] l = mid + 1 ; } else { // If pair sum is smaller than rest sum // our index will be in the Range [Lmid-1] r = mid - 1 ; } } // return index=-1 if a pair not exist with arr[i] // else return index such that arr[i]+arr[index] == // sum of rest of arr return index ; } // Function to check if a pair exist such their sum // equal to rest of the array or not static bool CheckPair ( int [] arr int n ) { int totalSum = 0 ; Array . Sort ( arr ); // sort arr for Binary search for ( int i = 0 ; i < n ; i ++ ) { totalSum += arr [ i ]; } // Finding total sum of the arr for ( int i = 0 ; i < n ; i ++ ) { // If index is -1 Means arr[i] can't pair with // any element else arr[i]+a[index] == sum of // rest of the arr int index = BinarySearch ( arr n i totalSum ); if ( index != - 1 ) { Console . WriteLine ( 'Pair elements are ' + arr [ i ] + ' and ' + arr [ index ]); return true ; } } return false ; // Return false if a pair not exist } // Driver Code static void Main ( string [] args ) { int [] arr = { 2 11 5 1 4 7 }; int n = arr . Length ; // Function call if ( ! CheckPair ( arr n )) { Console . WriteLine ( 'No pair found' ); } } }
JavaScript // JavaScript program for the above approach // function to find if a index exist in array such that // arr[index] + a[i] == Rest sum of the array function binarysearch ( arr n i TotalSum ){ let l = 0 ; let r = n - 1 ; let index = - 1 ; while ( l <= r ){ let mid = parseInt (( l + r ) / 2 ); let Pairsum = arr [ mid ] + arr [ i ]; let Restsum = TotalSum - Pairsum ; if ( Pairsum == Restsum ) { if ( index != i ) // checking a pair has same position or not { index = mid ; } //Then update index -1 to mid // Checking for adjacent element else if ( index == i && mid > 0 && arr [ mid - 1 ] == arr [ i ]) { index = mid - 1 ; } //Then update index -1 to mid-1 else if ( index == i && mid < n - 1 && arr [ mid + 1 ] == arr [ i ]) { index = mid + 1 ; } //Then update index-1 to mid+1 break ; } else if ( Pairsum > Restsum ) { // If pair sum is greater than rest sum our index will // be in the Range [mid+1R] l = mid + 1 ; } else { // If pair sum is smaller than rest sum our index will // be in the Range [Lmid-1] r = mid - 1 ; } } // return index=-1 if a pair not exist with arr[i] // else return index such that arr[i]+arr[index] == sum of rest of arr return index ; } // Function to check if a pair exist such their sum // equal to rest of the array or not function checkPair ( arr n ){ let Totalsum = 0 ; arr . sort ( function ( a b ){ return a - b }); for ( let i = 0 ; i < n ; i ++ ) { Totalsum += arr [ i ]; } //Finding total sum of the arr for ( let i = 0 ; i < n ; i ++ ) { // If index is -1 Means arr[i] can't pair with any element // else arr[i]+a[index] == sum of rest of the arr let index = binarysearch ( arr n i Totalsum ) ; if ( index != - 1 ) { console . log ( 'Pair elements are ' + arr [ i ] + ' and ' + arr [ index ]); return true ; } } return false ; //Return false if a pair not exist } // driver code to test above function let arr = [ 2 11 5 1 4 7 ]; let n = arr . length ; // function call if ( checkPair ( arr n ) == false ) console . log ( 'No Pair Found' ) // THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002)
Výstup
Pair elements are 11 and 4
Časová složitost: O(n * logn)
Pomocný prostor: O(1)
Vytvořit kvíz
