Dané pole celých čísel zjistěte, zda je možné odstranit právě jedno celé číslo z pole, které rozděluje pole na dvě podpole se stejným součtem.
Příklady:
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 naivní řešení by bylo zvážit všechny prvky pole a vypočítat jejich levý a pravý součet a vrátit true, pokud se levý a pravý součet shodne. Časová složitost tohoto řešení by byla O(n2).
The efektivní řešení zahrnuje výpočet součtu všech prvků pole předem. Potom pro každý prvek pole můžeme vypočítat jeho správný součet v čase O(1) pomocí celkového součtu prvků pole mínus součet prvků dosud nalezených. Časová složitost tohoto řešení by byla O(n) a jím využívaný pomocný prostor bude O(1).
Níže je implementace výše uvedeného přístupu:
C++
// C++ program to divide the array into two // subarrays with the same sum on removing // exactly one integer from the array #include
// 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 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# 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 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 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 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 ?> <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>
Výstup
The array can be divided intotwo subarrays with equal sum The two subarrays are - [ 6 ] [ 3 2 1 ]