Dada una array de n enteros positivos. Encuentre un elemento positivo mínimo para agregar a uno de los índices en la array de modo que pueda dividirse en dos subarreglos contiguos de sumas iguales. Muestra el elemento mínimo que se agregará y la posición donde se agregará. Si son posibles varias posiciones, devuelva la menor.
Ejemplos:
Entrada: arr[] = { 10, 1, 2, 3, 4 }
Salida: 0 0
Explicación: la array ya se puede dividir en dos subarreglos contiguos, es decir, {10} y {1, 2, 3, 4} con sumas iguales . Entonces necesitamos agregar 0 en cualquier posición. (la posición mínima es 0)
Entrada: arr[] = { 5, 4 }
Salida: 1 1
Explicación: necesitamos sumar 1 a 4 para que dos subarreglos sean {5},{5}, por lo que la salida es 1 1 (mínimo elemento y su posición donde se va a añadir.
Prerrequisitos: método de sumas de prefijos
1 (simple): un enfoque ingenuo es calcular la suma de elementos de (arr[0] a arr[i]) y (arr[i+1] a arr[n-1]), y en cada paso, encuentre la diferencia entre estas dos sumas, la diferencia mínima dará el elemento que se agregará.
Método 2 (Eficiente) : Un análisis cuidadoso sugiere que podemos usar el concepto de sumas de prefijos y sumas de sufijos. Calcule ambos y encuentre la diferencia absoluta entre prefixSum[i] (donde prefixSum[i] es la suma de los elementos del arreglo hasta la i-ésima posición) y suffixSum[i + 1] (donde suffixSum[i + 1] es la suma de los elementos del arreglo elementos desde (i + 1) ésima posición hasta la última posición).
Por ejemplo
arr 10 1 2 3 4 prefixSum 10 11 13 16 20 suffixSum 20 10 9 7 4 Absolute difference between suffixSum[i + 1] and prefixSum[i] 10 - 10 = 0 // minimum 11 - 9 = 1 13 - 7 = 6 16 - 4 = 12 Thus, minimum element is 0, for position, if prefixSum[i] is greater than suffixSum[i + 1], then position is "i + 1". else it's is "i".
A continuación se muestra la implementación del enfoque anterior.
C++
// CPP Program to find the minimum element to
// be added such that the array can be partitioned
// into two contiguous subarrays with equal sums
#include <bits/stdc++.h>
using namespace std;
// Structure to store the minimum element
// and its position
struct data {
int element;
int position;
};
struct data findMinElement(int arr[], int n)
{
struct data result;
// initialize prefix and suffix sum arrays with 0
int prefixSum[n] = { 0 };
int suffixSum[n] = { 0 };
prefixSum[0] = arr[0];
for (int i = 1; i < n; i++) {
// add current element to Sum
prefixSum[i] = prefixSum[i - 1] + arr[i];
}
suffixSum[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--) {
// add current element to Sum
suffixSum[i] = suffixSum[i + 1] + arr[i];
}
// initialize the minimum element to be a large value
int min = suffixSum[0];
int pos;
for (int i = 0; i < n - 1; i++) {
// check for the minimum absolute difference
// between current prefix sum and the next
// suffix sum element
if (abs(suffixSum[i + 1] - prefixSum[i]) < min) {
min = abs(suffixSum[i + 1] - prefixSum[i]);
// if prefixsum has a greater value then position
// is the next element, else it's the same element.
if (suffixSum[i + 1] < prefixSum[i]) pos = i + 1;
else pos = i;
}
}
// return the data in struct.
result.element = min;
result.position = pos;
return result;
}
// Driver Code
int main()
{
int arr[] = { 10, 1, 2, 3, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
struct data values;
values = findMinElement(arr, n);
cout << "Minimum element : " << values.element
<< endl << "Position : " << values.position;
return 0;
}
Java
// Java Program to find the minimum element to
// be added such that the array can be partitioned
// into two contiguous subarrays with equal sums
import java.util.*;
class GFG
{
// Structure to store the minimum element
// and its position
static class data
{
int element;
int position;
};
static data findMinElement(int arr[], int n)
{
data result=new data();
// initialize prefix and suffix sum arrays with 0
int []prefixSum = new int[n];
int []suffixSum = new int[n];
prefixSum[0] = arr[0];
for (int i = 1; i < n; i++)
{
// add current element to Sum
prefixSum[i] = prefixSum[i - 1] + arr[i];
}
suffixSum[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--)
{
// add current element to Sum
suffixSum[i] = suffixSum[i + 1] + arr[i];
}
// initialize the minimum element to be a large value
int min = suffixSum[0];
int pos=0;
for (int i = 0; i < n - 1; i++)
{
// check for the minimum absolute difference
// between current prefix sum and the next
// suffix sum element
if (Math.abs(suffixSum[i + 1] - prefixSum[i]) < min)
{
min = Math.abs(suffixSum[i + 1] - prefixSum[i]);
// if prefixsum has a greater value then position
// is the next element, else it's the same element.
if (suffixSum[i + 1] < prefixSum[i]) pos = i + 1;
else pos = i;
}
}
// return the data in struct.
result.element = min;
result.position = pos;
return result;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 10, 1, 2, 3, 4 };
int n = arr.length;
data values;
values = findMinElement(arr, n);
System.out.println("Minimum element : " + values.element
+ "\nPosition : " + values.position);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python Program to find the minimum element to
# be added such that the array can be partitioned
# into two contiguous subarrays with equal sums
# Class to store the minimum element
# and its position
class Data:
def __init__(self):
self.element = -1
self.position = -1
def findMinElement(arr, n):
result = Data()
# initialize prefix and suffix sum arrays with 0
prefixSum = [0]*n
suffixSum = [0]*n
prefixSum[0] = arr[0]
for i in range(1, n):
# add current element to Sum
prefixSum[i] = prefixSum[i-1] + arr[i]\
suffixSum[n-1] = arr[n-1]
for i in range(n-2, -1, -1):
# add current element to Sum
suffixSum[i] = suffixSum[i+1] + arr[i]
# initialize the minimum element to be a large value
mini = suffixSum[0]
pos = 0
for i in range(n-1):
# check for the minimum absolute difference
# between current prefix sum and the next
# suffix sum element
if abs(suffixSum[i+1]-prefixSum[i]) < mini:
mini = abs(suffixSum[i+1] - prefixSum[i])
# if prefixsum has a greater value then position
# is the next element, else it's the same element.
if suffixSum[i+1] < prefixSum[i]:
pos = i+1
else:
pos = i
# return the data in class.
result.element = mini
result.position = pos
return result
# Driver Code
if __name__ == "__main__":
arr = [10, 1, 2, 3, 4]
n = len(arr)
values = Data()
values = findMinElement(arr, n)
print("Minimum element :", values.element, "\nPosition :", values.position)
# This code is contributed by
# sanjeev2552
C#
// C# Program to find the minimum element
// to be added such that the array can be
// partitioned into two contiguous subarrays
// with equal sums
using System;
class GFG
{
// Structure to store the minimum element
// and its position
public class data
{
public int element;
public int position;
};
static data findMinElement(int []arr, int n)
{
data result = new data();
// initialize prefix and suffix
// sum arrays with 0
int []prefixSum = new int[n];
int []suffixSum = new int[n];
prefixSum[0] = arr[0];
for (int i = 1; i < n; i++)
{
// add current element to Sum
prefixSum[i] = prefixSum[i - 1] + arr[i];
}
suffixSum[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--)
{
// add current element to Sum
suffixSum[i] = suffixSum[i + 1] + arr[i];
}
// initialize the minimum element
// to be a large value
int min = suffixSum[0];
int pos = 0;
for (int i = 0; i < n - 1; i++)
{
// check for the minimum absolute difference
// between current prefix sum and the next
// suffix sum element
if (Math.Abs(suffixSum[i + 1] -
prefixSum[i]) < min)
{
min = Math.Abs(suffixSum[i + 1] -
prefixSum[i]);
// if prefixsum has a greater value then position
// is the next element, else it's the same element.
if (suffixSum[i + 1] < prefixSum[i])
pos = i + 1;
else
pos = i;
}
}
// return the data in struct.
result.element = min;
result.position = pos;
return result;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 10, 1, 2, 3, 4 };
int n = arr.Length;
data values;
values = findMinElement(arr, n);
Console.WriteLine("Minimum element : " +
values.element +
"\nPosition : " +
values.position);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript Program to find the minimum element to
// be added such that the array can be partitioned
// into two contiguous subarrays with equal sums
// Structure to store the minimum element
// and its position
class data
{
constructor(element, position){
this.element = element;
this.position = position;
}
};
function findMinElement(arr, n)
{
let result = new data();
// initialize prefix and suffix sum arrays with 0
let prefixSum = new Array(n);
let suffixSum = new Array(n);
prefixSum[0] = arr[0];
for (let i = 1; i < n; i++)
{
// add current element to Sum
prefixSum[i] = prefixSum[i - 1] + arr[i];
}
suffixSum[n - 1] = arr[n - 1];
for (let i = n - 2; i >= 0; i--)
{
// add current element to Sum
suffixSum[i] = suffixSum[i + 1] + arr[i];
}
// initialize the minimum element to be a large value
let min = suffixSum[0];
let pos=0;
for (let i = 0; i < n - 1; i++)
{
// check for the minimum absolute difference
// between current prefix sum and the next
// suffix sum element
if (Math.abs(suffixSum[i + 1] - prefixSum[i]) < min)
{
min = Math.abs(suffixSum[i + 1] - prefixSum[i]);
// if prefixsum has a greater value then position
// is the next element, else it's the same element.
if (suffixSum[i + 1] < prefixSum[i]) pos = i + 1;
else pos = i;
}
}
// return the data in struct.
result.element = min;
result.position = pos;
return result;
}
// Driver Code
let arr = [ 10, 1, 2, 3, 4 ];
let n = arr.length;
let values;
values = findMinElement(arr, n);
document.write("Minimum element : " +
values.element + "<br>Position : " + values.position);
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
Minimum element : 0 Position : 0
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por shubham bhuyan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA