Проверите да ли постоје два елемента у низу чији је збир једнак збиру остатака низа
Имамо низ целих бројева и морамо да пронађемо два таква елемента у низу тако да је збир ова два елемента једнак збиру остатака елемената у низу.
Примери:
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 А једноставно решење је размотрити сваки пар један по један пронаћи његов збир и упоредити збир са збиром осталих елемената. Ако пронађемо пар чији је збир једнак остатку елемената, исписујемо пар и враћамо труе. Временска сложеност овог решења је О(н 3 )
Ан ефикасно решење је пронаћи збир свих елемената низа. Нека овај збир буде 'збир'. Сада се задатак своди на проналажење пара чији је збир једнак збиру/2.
Друга оптимизација је да пар може постојати само ако је збир целог низа паран јер га у основи делимо на два дела са једнаким збиром.
- Пронађите збир целог низа. Нека овај збир буде 'збир'
- Ако је збир непаран, вратите нетачно.
- Пронађите пар са сумом једнаким 'суму/2' користећи методу засновану на хеширању овде као метод 2. Ако је пар пронађен, одштампајте га и вратите труе.
- Ако ниједан пар не постоји, вратите фалсе.
Испод је имплементација горњих корака.
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>
Излаз
Pair elements are 4 and 11
Временска сложеност: О(н) . унордеред_сет се имплементира помоћу хеширања. Временска сложеност хеш претрага и уметања се овде претпоставља као О(1).
Помоћни простор: О(н)
Још један ефикасан приступ (оптимизација простора): Прво ћемо сортирати низ за Бинарно претраживање . Затим ћемо поновити цео низ и проверити да ли постоји индекс у низу који је упарен са и тако да је арр[индек] + а[и] == Остала сума низа. Можемо да користимо бинарну претрагу да пронађемо индекс у низу тако што ћемо модификовати програм бинарне претраге. Ако постоји пар, одштампајте тај пар. иначе принт не постоји пар.
Испод је примена горњег приступа:
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)
Излаз
Pair elements are 11 and 4
Временска сложеност: О(н * пријава)
Помоћни простор: О(1)
Креирај квиз
