Descubra se a matriz pode ser dividida em duas submatrizes de soma igual
Dado um array de inteiros, descubra se é possível remover exatamente um inteiro do array que divide o array em dois subarrays com a mesma soma.
Exemplos:
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
UM solução ingênua seria considerar todos os elementos da matriz e calcular suas somas esquerda e direita e retornar verdadeiro se as somas esquerda e direita forem iguais. A complexidade de tempo desta solução seria O(n 2 ).
O solução eficiente envolve o cálculo antecipado da soma de todos os elementos da matriz. Então, para cada elemento do array, podemos calcular sua soma correta no tempo O(1) usando a soma total dos elementos do array menos a soma dos elementos encontrados até agora. A complexidade de tempo desta solução seria O(n) e o espaço auxiliar utilizado por ela será O(1).
Abaixo está a implementação da abordagem acima:
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>
Saída
The array can be divided intotwo subarrays with equal sum The two subarrays are - [ 6 ] [ 3 2 1 ]
