Finden Sie heraus, ob das Array in zwei Unterarrays gleicher Summe unterteilt werden kann
Finden Sie anhand eines Arrays von Ganzzahlen, ob es möglich ist, genau eine Ganzzahl aus dem Array zu entfernen, die das Array in zwei Unterarrays mit derselben Summe teilt.
Beispiele:
Input: arr = [6 2 3 2 1] Output: true Explanation: On removing element 2 at index 1 the array gets divided into two subarrays [6] and [3 2 1] having equal sum Input: arr = [6 1 3 2 5] Output: true Explanation: On removing element 3 at index 2 the array gets divided into two subarrays [6 1] and [2 5] having equal sum. Input: arr = [6 -2 -3 2 3] Output: true Explanation: On removing element 6 at index 0 the array gets divided into two sets [] and [-2 -3 2 3] having equal sum Input: arr = [6 -2 3 2 3] Output: false
A naive Lösung würde darin bestehen, alle Elemente des Arrays zu berücksichtigen, ihre linke und rechte Summe zu berechnen und „true“ zurückzugeben, wenn festgestellt wird, dass die linke und rechte Summe gleich sind. Die zeitliche Komplexität dieser Lösung wäre O(n 2 ).
Der effiziente Lösung beinhaltet die vorherige Berechnung der Summe aller Elemente des Arrays. Dann können wir für jedes Element des Arrays seine richtige Summe in O(1)-Zeit berechnen, indem wir die Gesamtsumme der Array-Elemente minus die Summe der bisher gefundenen Elemente verwenden. Die zeitliche Komplexität dieser Lösung wäre O(n) und der von ihr verwendete Hilfsraum wäre O(1).
Nachfolgend finden Sie die Umsetzung des oben genannten Ansatzes:
C++ // C++ program to divide the array into two // subarrays with the same sum on removing // exactly one integer from the array #include using namespace std ; // Utility function to print the sub-array void printSubArray ( int arr [] int start int end ) { cout < < '[ ' ; for ( int i = start ; i <= end ; i ++ ) cout < < arr [ i ] < < ' ' ; cout < < '] ' ; } // Function that divides the array into two subarrays // with the same sum bool divideArray ( int arr [] int n ) { // sum stores sum of all elements of the array int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) sum += arr [ i ]; // sum stores sum till previous index of the array int sum_so_far = 0 ; for ( int i = 0 ; i < n ; i ++ ) { // If on removing arr[i] we get equals left // and right half if ( 2 * sum_so_far + arr [ i ] == sum ) { cout < < 'The array can be divided into' 'two subarrays with equal sum n The' ' two subarrays are - ' ; printSubArray ( arr 0 i - 1 ); printSubArray ( arr i + 1 n - 1 ); return true ; } // add current element to sum_so_far sum_so_far += arr [ i ]; } // The array cannot be divided cout < < 'The array cannot be divided into two ' 'subarrays with equal sum' ; return false ; } // Driver code int main () { int arr [] = { 6 2 3 2 1 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); divideArray ( arr n ); return 0 ; }
Java // Java program to divide the array into two // subarrays with the same sum on removing // exactly one integer from the array import java.io.* ; class GFG { // Utility function to print the sub-array static void printSubArray ( int arr [] int start int end ) { System . out . print ( '[ ' ); for ( int i = start ; i <= end ; i ++ ) System . out . print ( arr [ i ] + ' ' ); System . out . print ( '] ' ); } // Function that divides the array into two subarrays // with the same sum static boolean divideArray ( int arr [] int n ) { // sum stores sum of all elements of the array int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) sum += arr [ i ] ; // sum stores sum till previous index of the array int sum_so_far = 0 ; for ( int i = 0 ; i < n ; i ++ ) { // If on removing arr[i] we get equals left // and right half if ( 2 * sum_so_far + arr [ i ] == sum ) { System . out . print ( 'The array can be divided into ' + 'two subarrays with equal sumnThe' + ' two subarrays are - ' ); printSubArray ( arr 0 i - 1 ); printSubArray ( arr i + 1 n - 1 ); return true ; } // add current element to sum_so_far sum_so_far += arr [ i ] ; } // The array cannot be divided System . out . println ( 'The array cannot be divided into two ' + 'subarrays with equal sum' ); return false ; } // Driver program public static void main ( String [] args ) { int arr [] = { 6 2 3 2 1 }; int n = arr . length ; divideArray ( arr n ); } } // This code is contributed by Pramod Kumar
Python3 ''' Python3 program to divide the array into two subarrays with the same sum on removing exactly one integer from the array''' # Utility function to print the sub-array def printSubArray ( arr start end ): print ( '[ ' end = '' ) for i in range ( start end + 1 ): print ( arr [ i ] end = ' ' ) print ( ']' end = '' ) # Function that divides the array into # two subarrays with the same sum def divideArray ( arr n ): # sum stores sum of all # elements of the array sum = 0 for i in range ( 0 n ): sum += arr [ i ] # sum stores sum till previous # index of the array sum_so_far = 0 for i in range ( 0 n ): # If on removing arr[i] we get # equals left and right half if 2 * sum_so_far + arr [ i ] == sum : print ( 'The array can be divided into' 'two subarrays with equal sum' ) print ( 'two subarrays are -' end = '' ) printSubArray ( arr 0 i - 1 ) printSubArray ( arr i + 1 n - 1 ) return True # add current element to sum_so_far sum_so_far += arr [ i ] # The array cannot be divided print ( 'The array cannot be divided into' 'two subarrays with equal sum' end = '' ) return False # Driver code arr = [ 6 2 3 2 1 ] n = len ( arr ) divideArray ( arr n ) # This code is contributed by Shreyanshi Arun
C# // C# program to divide the array into two // subarrays with the same sum on removing // exactly one integer from the array using System ; class GFG { // Utility function to print the sub-array static void printSubArray ( int [] arr int start int end ) { Console . Write ( '[ ' ); for ( int i = start ; i <= end ; i ++ ) Console . Write ( arr [ i ] + ' ' ); Console . Write ( '] ' ); } // Function that divides the array into // two subarrays with the same sum static bool divideArray ( int [] arr int n ) { // sum stores sum of all elements of // the array int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) sum += arr [ i ]; // sum stores sum till previous index // of the array int sum_so_far = 0 ; for ( int i = 0 ; i < n ; i ++ ) { // If on removing arr[i] we get // equals left and right half if ( 2 * sum_so_far + arr [ i ] == sum ) { Console . Write ( 'The array can be' + ' divided into two subarrays' + ' with equal sumnThe two' + ' subarrays are - ' ); printSubArray ( arr 0 i - 1 ); printSubArray ( arr i + 1 n - 1 ); return true ; } // add current element to sum_so_far sum_so_far += arr [ i ]; } // The array cannot be divided Console . WriteLine ( 'The array cannot be' + ' divided into two subarrays with ' + 'equal sum' ); return false ; } // Driver program public static void Main () { int [] arr = { 6 2 3 2 1 }; int n = arr . Length ; divideArray ( arr n ); } } // This code is contributed by anuj_67.
PHP // PHP program to divide the array into two // subarrays with the same sum on removing // exactly one integer from the array // Utility function to print the sub-array function printSubArray ( $arr $start $end ) { echo '[ ' ; for ( $i = $start ; $i <= $end ; $i ++ ) echo $arr [ $i ] . ' ' ; echo '] ' ; } // Function that divides the // array into two subarrays // with the same sum function divideArray ( $arr $n ) { // sum stores sum of all // elements of the array $sum = 0 ; for ( $i = 0 ; $i < $n ; $i ++ ) $sum += $arr [ $i ]; // sum stores sum till previous // index of the array $sum_so_far = 0 ; for ( $i = 0 ; $i < $n ; $i ++ ) { // If on removing arr[i] // we get equals left // and right half if ( 2 * $sum_so_far + $arr [ $i ] == $sum ) { echo 'The array can be divided into' . 'two subarrays with equal sum n The' . ' two subarrays are - ' ; printSubArray ( $arr 0 $i - 1 ); printSubArray ( $arr $i + 1 $n - 1 ); return true ; } // add current element // to sum_so_far $sum_so_far += $arr [ $i ]; } // The array cannot be divided echo 'The array cannot be divided into two ' . 'subarrays with equal sum' ; return false ; } // Driver code $arr = array ( 6 2 3 2 1 ); $n = sizeof ( $arr ); divideArray ( $arr $n ); // This code is contributed by Anuj_67 ?>
JavaScript < script > // JavaScript program to divide the array into two // subarrays with the same sum on removing // exactly one integer from the array // Utility function to print the sub-array function printSubArray ( arr start end ) { document . write ( '[ ' ); for ( let i = start ; i <= end ; i ++ ) document . write ( arr [ i ] + ' ' ); document . write ( '] ' ); } // Function that divides the array into // two subarrays with the same sum function divideArray ( arr n ) { // sum stores sum of all elements of // the array let sum = 0 ; for ( let i = 0 ; i < n ; i ++ ) sum += arr [ i ]; // sum stores sum till previous index // of the array let sum_so_far = 0 ; for ( let i = 0 ; i < n ; i ++ ) { // If on removing arr[i] we get // equals left and right half if ( 2 * sum_so_far + arr [ i ] == sum ) { document . write ( 'The array can be' + ' divided into two subarrays' + ' with equal sum ' + ' ' + 'The two' + ' sets are - ' ); printSubArray ( arr 0 i - 1 ); printSubArray ( arr i + 1 n - 1 ); return true ; } // add current element to sum_so_far sum_so_far += arr [ i ]; } // The array cannot be divided document . write ( 'The array cannot be' + ' divided into two subarrays with ' + 'equal sum' + ' ' ); return false ; } let arr = [ 6 2 3 2 1 ]; let n = arr . length ; divideArray ( arr n ); < /script>
Ausgabe
The array can be divided intotwo subarrays with equal sum The two subarrays are - [ 6 ] [ 3 2 1 ]
