Dada una array de enteros positivos, encuentre el entero no negativo más pequeño (es decir, mayor que o igual a cero) que se puede colocar entre dos elementos cualesquiera de la array de manera que la suma de los elementos en la subarreferencia que ocurren antes sea igual a la suma de los elementos que aparecen en el subarreglo que le sigue, con el entero recién colocado incluido en cualquiera de los dos subarreglos.
Ejemplos:
Entrada : arr = {3, 2, 1, 5, 7, 8}
Salida : 4
Explicación : El número más pequeño posible que podemos insertar es 4, en la posición 5 (es decir, entre 5 y 7) como parte del primer subarreglo, por lo que que la suma de los dos subarreglos se vuelve igual a 3+2+1+5+4=15 y 7+8=15.
Entrada : arr = {3, 2, 2, 3}
Salida : 0
Explicación : La suma igual a 5 se obtiene sumando los primeros dos elementos y los últimos dos elementos como subarreglos separados sin insertar ningún número adicional. Por lo tanto, el entero más pequeño que se insertará es 0 en la posición 3.
Para dividir el arreglo de tal manera que dé dos subarreglos con sumas iguales de sus respectivos elementos, un enfoque muy simple y directo es seguir agregando elementos desde el comienzo del arreglo, uno por uno y encontrar la diferencia entre sus suma y suma del resto de los elementos. Usamos un bucle iterativo para hacerlo. Para los índices de array 0 a N-1, seguimos agregando elementos de izquierda a derecha y encontramos su diferencia con la suma restante. Durante la primera iteración, la diferencia obtenida se considera mínima para poder realizar posteriores comparaciones. Para el resto de iteraciones, si la diferencia obtenida es menor que el mínimo considerado anteriormente, actualizamos el valor de mínimo. Hasta el final del bucle, finalmente obtenemos el número mínimo que se puede sumar.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the smallest
// number to be added to make the
// sum of left and right subarrays equal
#include<bits/stdc++.h>
using namespace std;
// Function to find the minimum
// value to be added
int findMinEqualSums(int a[], int N)
{
// Variable to store entire
// array sum
int sum = 0;
for (int i = 0; i < N; i++)
{
sum += a[i];
}
// Variables to store sum of
// subarray1 and subarray 2
int sum1 = 0, sum2 = 0;
// minimum value to be added
int min = INT_MAX;
// Traverse through the array
for (int i = 0; i < N; i++)
{
// Sum of both halves
sum1 += a[i];
sum2 = sum - sum1;
// Calculate minimum number
// to be added
if (abs(sum1 - sum2) < min)
{
min = abs(sum1 - sum2);
}
if (min == 0)
{
break;
}
}
return min;
}
// Driver code
int main()
{
int a[] = { 3, 2, 1, 5, 7, 8 };
// Length of array
int N = sizeof(a) / sizeof(a[0]);
cout << (findMinEqualSums(a, N));
}
// This code is contributed
// by ChitraNayal
Java
// Java program to find the smallest
// number to be added to make the
// sum of left and right subarrays equal
import java.io.*;
import java.util.*;
class GFG
{
// Function to find the minimum
// value to be added
static int findMinEqualSums(int[] a, int N)
{
// Variable to store
// entire array sum
int sum = 0;
for (int i = 0; i < N; i++)
{
sum += a[i];
}
// Variables to store sum of
// subarray1 and subarray 2
int sum1 = 0, sum2 = 0;
// minimum value to be added
int min = Integer.MAX_VALUE;
// Traverse through the array
for (int i = 0; i < N; i++)
{
// Sum of both halves
sum1 += a[i];
sum2 = sum - sum1;
// Calculate minimum number
// to be added
if (Math.abs(sum1 - sum2) < min)
{
min = Math.abs(sum1 - sum2);
}
if (min == 0)
{
break;
}
}
return min;
}
// Driver code
public static void main(String args[])
{
int[] a = { 3, 2, 1, 5, 7, 8 };
// Length of array
int N = a.length;
System.out.println(findMinEqualSums(a, N));
}
}
Python3
import sys # Python3 program to find the smallest # number to be added to make the # sum of left and right subarrays equal # Function to find the minimum # value to be added def findMinEqualSums(a, N): # Variable to store entire # array sum sum = 0 for i in range(0,N): sum = sum+a[i] # Variables to store sum of # subarray1 and subarray 2 sum1 = 0 sum2 = 0 # minimum value to be added min = sys.maxsize # Traverse through the array for i in range(0, N-1): # Sum of both halves sum1 += a[i] sum2 = sum - sum1 # Calculate minimum number # to be added if (abs(sum1 - sum2) < min): min = abs(sum1 - sum2) if (min == 0) : break return min # Driver code if __name__=='__main__': a = [3, 2, 1, 5, 7, 8] # Length of array N = len(a) print(findMinEqualSums(a, N)) # This code is contributed # by Shivi_Aggarwal
C#
// C# program to find the smallest
// number to be added to make the
// sum of left and right subarrays equal
using System;
class GFG
{
// Function to find the minimum
// value to be added
static int findMinEqualSums(int[] a, int N)
{
// Variable to store
// entire array sum
int sum = 0;
for (int i = 0; i < N; i++)
{
sum += a[i];
}
// Variables to store sum of
// subarray1 and subarray 2
int sum1 = 0, sum2 = 0;
// minimum value to be added
int min = int.MaxValue;
// Traverse through the array
for (int i = 0; i < N; i++)
{
// Sum of both halves
sum1 += a[i];
sum2 = sum - sum1;
// Calculate minimum number
// to be added
if (Math.Abs(sum1 - sum2) < min)
{
min = Math.Abs(sum1 - sum2);
}
if (min == 0)
{
break;
}
}
return min;
}
// Driver code
public static void Main()
{
int[] a = { 3, 2, 1, 5, 7, 8 };
// Length of array
int N = a.Length;
Console.WriteLine(findMinEqualSums(a, N));
}
}
// This code is contributed by shs
PHP
<?php
// PHP program to find the smallest
// number to be added to make the
// sum of left and right subarrays equal
// Function to find the minimum
// value to be added
function findMinEqualSums($a, $N)
{
// Variable to store entire
// array sum
$sum = 0;
for ($i = 0; $i < $N; $i++)
{
$sum += $a[$i];
}
// Variables to store sum of
// subarray1 and subarray 2
$sum1 = 0; $sum2 = 0;
// minimum value to be added
$min = PHP_INT_MAX;
// Traverse through the array
for ($i = 0; $i < $N; $i++)
{
// Sum of both halves
$sum1 += $a[$i];
$sum2 = $sum - $sum1;
// Calculate minimum number
// to be added
if (abs($sum1 - $sum2) < $min)
{
$min = abs($sum1 - $sum2);
}
if ($min == 0)
{
break;
}
}
return $min;
}
// Driver code
$a = array( 3, 2, 1, 5, 7, 8 );
// Length of array
$N = count($a);
echo (findMinEqualSums($a, $N));
// This code is contributed
// shs
?>
Javascript
<script>
// Javascript program to find the smallest
// number to be added to make the
// sum of left and right subarrays equal
// Function to find the minimum
// value to be added
function findMinEqualSums(a,N)
{
// Variable to store
// entire array sum
let sum = 0;
for (let i = 0; i < N; i++)
{
sum += a[i];
}
// Variables to store sum of
// subarray1 and subarray 2
let sum1 = 0, sum2 = 0;
// minimum value to be added
let min = Number.MAX_VALUE;
// Traverse through the array
for (let i = 0; i < N; i++)
{
// Sum of both halves
sum1 += a[i];
sum2 = sum - sum1;
// Calculate minimum number
// to be added
if (Math.abs(sum1 - sum2) < min)
{
min = Math.abs(sum1 - sum2);
}
if (min == 0)
{
break;
}
}
return min;
}
// Driver code
let a=[3, 2, 1, 5, 7, 8];
// Length of array
let N = a.length;
document.write(findMinEqualSums(a, N));
// This code is contributed by avanitrachhadiya2155
</script>
4
Tiempo Complejidad : O(n)
Espacio Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por rachana soma y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA