Dada una array de N enteros positivos, la tarea es encontrar el entero positivo más pequeño que se puede colocar entre dos elementos cualesquiera de la array de tal manera que la suma de los elementos en la subarreferencia que se encuentran antes de él sea igual a la suma de los elementos que se encuentran en el subarreglo que le sigue, con el entero recién colocado incluido en cualquiera de los dos subarreglos.
Ejemplos:
Input : arr = { 3, 2, 1, 5, 7, 8 }
Output : 4
Explanation
The smallest possible number that can be inserted is 4 between elements 5 and 7
as part of the first subarray so that the sum of the two subarrays becomes
equal i.e, 3 + 2 + 1 + 5 + 4 = 15 and 7 + 8 = 15.
Input : arr = { 3, 2, 2, 3 }
Output : No Extra Element required
Explanation
Equal sum of 5 is obtained by adding the first two elements and last two elements
as separate subarrays without inserting any extra number.
Enfoque: Sea la suma de toda la array por S. La idea es encontrar la suma de la izquierda hasta el índice i (incluyéndolo). Sea esta suma L. Ahora la suma del subarreglo arr i + 1 ……. N es S – L. Sea esta suma R. Dado que se supone que la suma de los dos subarreglos es igual, la mayor de las dos sumas L y R obtenidas anteriormente debe reducirse al valor de la suma menor entre estos dos y la diferencia entre la suma mayor. suma y la suma menor, será el valor del entero positivo requerido, que debe minimizarse.
Habrá dos condiciones durante la travesía:
- L > R : el valor de los elementos requeridos para igualar la suma de los subarreglos izquierdo y derecho será L – R y si este valor es menor que el valor del elemento mínimo calculado previamente, entonces este se convierte en el elemento mínimo requerido. Obviamente, este elemento sería parte del subarreglo que tiene una suma menor, es decir, el subarreglo correcto es este caso
- R > L : el valor de los elementos requeridos para igualar la suma de los subarreglos izquierdo y derecho será R – L y si este valor es menor que el valor del elemento mínimo calculado previamente, entonces este se convierte en el elemento mínimo requerido. Obviamente, este elemento sería parte del subarreglo que tiene una suma menor, es decir, el subarreglo izquierdo es este caso
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the minimum non-negative
// element required to split the array
// into two subarrays with equal sum
#include <bits/stdc++.h>
using namespace std;
// Function to return the minimum positive integer
// required to split array into two subarrays with equal sums
int findMinimumSplit(int arr[], int n)
{
// Find the sum of whole array
int totalSum = 0;
for (int i = 0; i < n; i++) {
totalSum += arr[i];
}
// leftSubarraySum stores the sum of arr[0....i] and
// rightSubarraySum stores the sum of arr[i + 1....n]
int leftSubarraySum = 0;
int rightSubarraySum = 0;
int minimumElement = INT_MAX;
for (int i = 0; i < n - 1; i++) {
// Find the left subarray sum and
// corresponding right subarray sum
leftSubarraySum += arr[i];
rightSubarraySum = totalSum - leftSubarraySum;
// if left subarray has larger sum, find the
// element to be included in the right subarray
// to make their sums equal
if (leftSubarraySum > rightSubarraySum) {
int element = leftSubarraySum - rightSubarraySum;
if (element < minimumElement) {
minimumElement = element;
}
}
// the Right subarray has larger sum,
// find the element to be included in
// the left subarray to make their sums equal
else {
int element = rightSubarraySum - leftSubarraySum;
if (element < minimumElement) {
minimumElement = element;
}
}
}
return minimumElement;
}
// Driver Code
int main()
{
int arr[] = { 3, 2, 1, 5, 7, 8 };
int n = sizeof(arr) / sizeof(arr[0]);
int minimumElement = findMinimumSplit(arr, n);
// If 0 then no insertion is required
if (minimumElement == 0) {
cout << "No Extra Element Required" << endl;
}
else {
cout << minimumElement << endl;
}
return 0;
}
Java
// Java program to find the minimum non-negative
// element required to split the array
// into two subarrays with equal sum
import java.util.*;
class solution
{
// Function to return the minimum positive integer
// required to split array into two subarrays with equal sums
static int findMinimumSplit(int arr[], int n)
{
// Find the sum of whole array
int totalSum = 0;
for (int i = 0; i < n; i++) {
totalSum += arr[i];
}
// leftSubarraySum stores the sum of arr[0....i] and
// rightSubarraySum stores the sum of arr[i + 1....n]
int leftSubarraySum = 0;
int rightSubarraySum = 0;
int minimumElement = Integer.MAX_VALUE;
for (int i = 0; i < n - 1; i++) {
// Find the left subarray sum and
// corresponding right subarray sum
leftSubarraySum += arr[i];
rightSubarraySum = totalSum - leftSubarraySum;
// if left subarray has larger sum, find the
// element to be included in the right subarray
// to make their sums equal
if (leftSubarraySum > rightSubarraySum) {
int element = leftSubarraySum - rightSubarraySum;
if (element < minimumElement) {
minimumElement = element;
}
}
// the Right subarray has larger sum,
// find the element to be included in
// the left subarray to make their sums equal
else {
int element = rightSubarraySum - leftSubarraySum;
if (element < minimumElement) {
minimumElement = element;
}
}
}
return minimumElement;
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 3, 2, 1, 5, 7, 8 };
int n = arr.length;
int minimumElement = findMinimumSplit(arr, n);
// If 0 then no insertion is required
if (minimumElement == 0) {
System.out.println("No Extra Element Required");
}
else {
System.out.println(minimumElement);
}
}
}
// This code is contributed by
// Sanjit_Prasad
Python 3
# Python 3 program to find the minimum # non-negative element required to split # the array into two subarrays with equal sum import sys # Function to return the minimum positive # integer required to split array into two # subarrays with equal sums def findMinimumSplit(arr, n): # Find the sum of whole array totalSum = 0 for i in range(n): totalSum += arr[i] # leftSubarraySum stores the sum of # arr[0....i] and rightSubarraySum # stores the sum of arr[i + 1....n] leftSubarraySum = 0 rightSubarraySum = 0 minimumElement = sys.maxsize for i in range(n - 1): # Find the left subarray sum and # corresponding right subarray sum leftSubarraySum += arr[i] rightSubarraySum = totalSum - leftSubarraySum # if left subarray has larger sum, find the # element to be included in the right # subarray to make their sums equal if (leftSubarraySum > rightSubarraySum): element = leftSubarraySum - rightSubarraySum if (element < minimumElement) : minimumElement = element # the Right subarray has larger sum, # find the element to be included in # the left subarray to make their sums equal else : element = rightSubarraySum - leftSubarraySum if (element < minimumElement) : minimumElement = element return minimumElement # Driver Code if __name__ == "__main__": arr = [ 3, 2, 1, 5, 7, 8 ] n = len(arr) minimumElement = findMinimumSplit(arr, n) # If 0 then no insertion is required if (minimumElement == 0): print( "No Extra Element Required" ) else : print(minimumElement) # This code is contributed by ita_c
C#
// C# program to find the
// minimum non-negative
// element required to split
// the array into two
// subarrays with equal sum
using System;
class GFG
{
// Function to return the
// minimum positive integer
// required to split array
// into two subarrays with
// equal sums
static int findMinimumSplit(int []arr,
int n)
{
// Find the sum
// of whole array
int totalSum = 0;
for (int i = 0; i < n; i++)
{
totalSum += arr[i];
}
// leftSubarraySum stores
// the sum of arr[0....i]
// and rightSubarraySum
// stores the sum of
// arr[i + 1....n]
int leftSubarraySum = 0;
int rightSubarraySum = 0;
int minimumElement = int.MaxValue;
for (int i = 0; i < n - 1; i++)
{
// Find the left subarray
// sum and corresponding
// right subarray sum
leftSubarraySum += arr[i];
rightSubarraySum = totalSum -
leftSubarraySum;
// if left subarray has
// larger sum, find the
// element to be included
// in the right subarray
// to make their sums equal
if (leftSubarraySum >
rightSubarraySum)
{
int element = leftSubarraySum -
rightSubarraySum;
if (element < minimumElement)
{
minimumElement = element;
}
}
// the Right subarray has
// larger sum, find the
// element to be included
// in the left subarray to
// make their sums equal
else
{
int element = rightSubarraySum -
leftSubarraySum;
if (element < minimumElement)
{
minimumElement = element;
}
}
}
return minimumElement;
}
// Driver Code
public static void Main ()
{
int []arr = {3, 2, 1, 5, 7, 8};
int n = arr.Length;
int minimumElement =
findMinimumSplit(arr, n);
// If 0 then no
// insertion is required
if (minimumElement == 0)
{
Console.WriteLine("No Extra " +
"Element Required");
}
else
{
Console.WriteLine(minimumElement);
}
}
}
// This code is contributed
// by anuj_67.
Javascript
<script>
// Javascript program to find the minimum non-negative
// element required to split the array
// into two subarrays with equal sum
// Function to return the minimum positive integer
// required to split array into two subarrays with equal sums
function findMinimumSplit(arr,n)
{
// Find the sum of whole array
let totalSum = 0;
for (let i = 0; i < n; i++) {
totalSum += arr[i];
}
// leftSubarraySum stores the sum of arr[0....i] and
// rightSubarraySum stores the sum of arr[i + 1....n]
let leftSubarraySum = 0;
let rightSubarraySum = 0;
let minimumElement = Number.MAX_VALUE;
for (let i = 0; i < n - 1; i++) {
// Find the left subarray sum and
// corresponding right subarray sum
leftSubarraySum += arr[i];
rightSubarraySum = totalSum - leftSubarraySum;
// if left subarray has larger sum, find the
// element to be included in the right subarray
// to make their sums equal
if (leftSubarraySum > rightSubarraySum) {
let element = leftSubarraySum - rightSubarraySum;
if (element < minimumElement) {
minimumElement = element;
}
}
// the Right subarray has larger sum,
// find the element to be included in
// the left subarray to make their sums equal
else {
let element = rightSubarraySum - leftSubarraySum;
if (element < minimumElement) {
minimumElement = element;
}
}
}
return minimumElement;
}
// Driver Code
let arr=[3, 2, 1, 5, 7, 8];
let n = arr.length;
let minimumElement = findMinimumSplit(arr, n);
// If 0 then no insertion is required
if (minimumElement == 0) {
document.write("No Extra Element Required");
}
else {
document.write(minimumElement);
}
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
4
Complejidad de tiempo: O(N) donde N es el número de elementos en la array.