Dada una array de números positivos y negativos. La tarea es encontrar un punto de partición tal que ninguno de los elementos de la array izquierda esté en la array derecha. Si hay varias particiones, encuentre la partición en la que la diferencia absoluta entre la suma de la array izquierda y la suma de la array derecha (|suma izquierda – suma derecha |) con respecto al punto de partición es mínima. En el caso de varios puntos, imprima el primer punto de partición desde la izquierda, que es (último índice de la array izquierda y primer índice de la array derecha)/2. Considere la indexación basada en 1. La array izquierda y derecha en la partición debe tener un mínimo de 1 elemento y un máximo de n-1 elementos. Imprime -1 si no es posible ninguna partición.
Ejemplos:
Entrada: a[] = {1, 2, -1, 2, 3}
Salida: 1
Array izquierda = {1, 2, -1, 2}
Array derecha = {3}
Sumleft = 4, Sumright = 3
Diferencia = 1 que es el mínimo posible
Entrada: a[] = {1, 2, 3, 1}
Salida: -1
Un enfoque ingenuo será recorrer de izquierda a derecha cada índice y verificar si la partición es posible o no en ese índice. Si la partición es posible, verifique si la diferencia absoluta entre la suma de un elemento de la array izquierda y el elemento de la array derecha es menor que el valor obtenido anteriormente en la partición. Después de encontrar el punto de partición, encuentre con avidez |sum left – sum right | .
Complejidad de tiempo: O(N 2 )
Una solución eficiente será almacenar el último índice de cada elemento que aparece en un mapa hash. Dado que los valores de los elementos son grandes, no se puede utilizar la indexación directa. Crea un prefijo[] yarray de sufijos [] que almacena la suma de prefijos y la suma de sufijos respectivamente. Inicialice un recuento de variables como 0. Itere para todos los elementos de la array. Un punto común de observación es, al atravesar si la última no ocurrencia del elemento presente (A i ) no es i en sí mismo, entonces no podemos tener una partición entre i y la última ocurrencia del elemento. Durante el recorrido, almacene el máximo de la última aparición del elemento, ya que la partición no se puede realizar hasta entonces.
Una vez que el recuento es yo mismo, podemos tener una partición, ahora, si hay varias particiones, elija min |sum left – sum right |.
Nota: el uso de map en lugar de unordered_map puede causar TLE.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for SP- partition
#include <bits/stdc++.h>
using namespace std;
// Function to find the partition
void partition(int a[], int n)
{
unordered_map<long long, long long> mpp;
// mark the last occurrence of every element
for (int i = 0; i < n; i++)
mpp[a[i]] = i;
// calculate the prefix sum
long long presum[n];
presum[0] = a[0];
for (int i = 1; i < n; i++)
presum[i] = presum[i - 1] + a[i];
// calculate the suffix sum
long long sufsum[n];
sufsum[n - 1] = a[n - 1];
for (int i = n - 2; i >= 0; i--) {
sufsum[i] = sufsum[i + 1] + a[i];
}
// Check if partition is possible
bool possible = false;
// Stores the absolute difference
long long ans = 1e18;
// stores the last index till
// which there can not be any partition
long long count = 0;
// Stores the partition
long long index = -1;
// Check if partition is possible or not
// donot check for the last element
// as partition is not possible
for (int i = 0; i < n - 1; i++) {
// takes an element and checks it last occurrence
// stores the maximum of the last occurrence
// where partition can be done
count = max(count, mpp[a[i]]);
// if partition is possible
if (count == i) {
// partition is possible
possible = true;
// stores the left array sum
long long sumleft = presum[i];
// stores the right array sum
long long sumright = sufsum[i + 1];
// check if the difference is minimum
if ((abs(sumleft - sumright)) < ans) {
ans = abs(sumleft - sumright);
index = i + 1;
}
}
}
// is partition is possible or not
if (possible)
cout << index << ".5" << endl;
else
cout << -1 << endl;
}
// Driver Code-
int main()
{
int a[] = { 1, 2, -1, 2, 3 };
int n = sizeof(a) / sizeof(a[0]);
partition(a, n);
return 0;
}
Java
// Java program for SP- partition
import java.util.*;
class GFG
{
// Function to find the partition
static void partition(int a[], int n)
{
Map<Integer,
Integer> mpp = new HashMap<>();
// mark the last occurrence of
// every element
for (int i = 0; i < n; i++)
mpp.put(a[i], i);
// calculate the prefix sum
long[] presum = new long[n];
presum[0] = a[0];
for (int i = 1; i < n; i++)
presum[i] = presum[i - 1] + a[i];
// calculate the suffix sum
long[] sufsum = new long[n];
sufsum[n - 1] = a[n - 1];
for (int i = n - 2; i >= 0; i--)
{
sufsum[i] = sufsum[i + 1] + a[i];
}
// Check if partition is possible
boolean possible = false;
// Stores the absolute difference
long ans = (long) 1e18;
// stores the last index till
// which there can not be any partition
long count = 0;
// Stores the partition
long index = -1;
// Check if partition is possible or not
// donot check for the last element
// as partition is not possible
for (int i = 0; i < n - 1; i++)
{
// takes an element and checks its
// last occurrence, stores the maximum
// of the last occurrence where
// partition can be done
count = Math.max(count, mpp.get(a[i]));
// if partition is possible
if (count == i)
{
// partition is possible
possible = true;
// stores the left array sum
long sumleft = presum[i];
// stores the right array sum
long sumright = sufsum[i + 1];
// check if the difference is minimum
if ((Math.abs(sumleft - sumright)) < ans)
{
ans = Math.abs(sumleft - sumright);
index = i + 1;
}
}
}
// is partition is possible or not
if (possible)
System.out.print(index + ".5" + "\n");
else
System.out.print(-1 + "\n");
}
// Driver Code
public static void main(String[] args)
{
int a[] = { 1, 2, -1, 2, 3 };
int n = a.length;
partition(a, n);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python program for SP- partition
# Function to find the partition
def partition(a: list, n: int):
mpp = dict()
# mark the last occurrence of every element
for i in range(n):
mpp[a[i]] = i
# calculate the prefix sum
preSum = [0] * n
preSum[0] = a[0]
for i in range(1, n):
preSum[i] = preSum[i - 1] + a[i]
# calculate the suffix sum
sufSum = [0] * n
sufSum[n - 1] = a[n - 1]
for i in range(n - 2, -1, -1):
sufSum[i] = sufSum[i + 1] + a[i]
# Check if partition is possible
possible = False
# Stores the absolute difference
ans = int(1e18)
# stores the last index till
# which there can not be any partition
count = 0
# Stores the partition
index = -1
# Check if partition is possible or not
# donot check for the last element
# as partition is not possible
for i in range(n - 1):
# takes an element and checks it last occurrence
# stores the maximum of the last occurrence
# where partition can be done
count = max(count, mpp[a[i]])
# if partition is possible
if count == i:
# partition is possible
possible = True
# stores the left array sum
sumleft = preSum[i]
# stores the right array sum
sumright = sufSum[i + 1]
# check if the difference is minimum
if abs(sumleft - sumright) < ans:
ans = abs(sumleft - sumright)
index = i + 1
# is partition is possible or not
if possible:
print("%d.5" % index)
else:
print("-1")
# Driver Code
if __name__ == "__main__":
a = [1, 2, -1, 2, 3]
n = len(a)
partition(a, n)
# This code is contributed by
# sanjeev2552
C#
// C# program for SP- partition
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the partition
static void partition(int []a, int n)
{
Dictionary<int,
int> mpp = new Dictionary<int,
int>();
// mark the last occurrence of
// every element
for (int i = 0; i < n; i++)
if(mpp.ContainsKey(a[i]))
mpp[a[i]] = i;
else
mpp.Add(a[i], i);
// calculate the prefix sum
long[] presum = new long[n];
presum[0] = a[0];
for (int i = 1; i < n; i++)
presum[i] = presum[i - 1] + a[i];
// calculate the suffix sum
long[] sufsum = new long[n];
sufsum[n - 1] = a[n - 1];
for (int i = n - 2; i >= 0; i--)
{
sufsum[i] = sufsum[i + 1] + a[i];
}
// Check if partition is possible
bool possible = false;
// Stores the absolute difference
long ans = (long) 1e18;
// stores the last index till which
// there can not be any partition
long count = 0;
// Stores the partition
long index = -1;
// Check if partition is possible or not
// donot check for the last element
// as partition is not possible
for (int i = 0; i < n - 1; i++)
{
// takes an element and checks its
// last occurrence, stores the maximum
// of the last occurrence where
// partition can be done
count = Math.Max(count, mpp[a[i]]);
// if partition is possible
if (count == i)
{
// partition is possible
possible = true;
// stores the left array sum
long sumleft = presum[i];
// stores the right array sum
long sumright = sufsum[i + 1];
// check if the difference is minimum
if ((Math.Abs(sumleft -
sumright)) < ans)
{
ans = Math.Abs(sumleft - sumright);
index = i + 1;
}
}
}
// is partition is possible or not
if (possible)
Console.Write(index + ".5" + "\n");
else
Console.Write(-1 + "\n");
}
// Driver Code
public static void Main(String[] args)
{
int []a = { 1, 2, -1, 2, 3 };
int n = a.Length;
partition(a, n);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program for SP- partition
// Function to find the partition
function partition(a, n) {
let mpp = new Map();
// mark the last occurrence of every element
for (let i = 0; i < n; i++)
mpp.set(a[i], i);
// calculate the prefix sum
let presum = new Array(n);
presum[0] = a[0];
for (let i = 1; i < n; i++)
presum[i] = presum[i - 1] + a[i];
// calculate the suffix sum
let sufsum = new Array(n);
sufsum[n - 1] = a[n - 1];
for (let i = n - 2; i >= 0; i--) {
sufsum[i] = sufsum[i + 1] + a[i];
}
// Check if partition is possible
let possible = false;
// Stores the absolute difference
let ans = Number.MAX_SAFE_INTEGER;
// stores the last index till
// which there can not be any partition
let count = 0;
// Stores the partition
let index = -1;
// Check if partition is possible or not
// donot check for the last element
// as partition is not possible
for (let i = 0; i < n - 1; i++) {
// takes an element and checks it last occurrence
// stores the maximum of the last occurrence
// where partition can be done
count = Math.max(count, mpp.get(a[i]));
// if partition is possible
if (count == i) {
// partition is possible
possible = true;
// stores the left array sum
let sumleft = presum[i];
// stores the right array sum
let sumright = sufsum[i + 1];
// check if the difference is minimum
if ((Math.abs(sumleft - sumright)) < ans) {
ans = Math.abs(sumleft - sumright);
index = i + 1;
}
}
}
// is partition is possible or not
if (possible)
document.write(index + ".5" + "<br>");
else
document.write(-1 + "<br>");
}
// Driver Code-
let a = [1, 2, -1, 2, 3];
let n = a.length;
partition(a, n);
// This code is contributed by saurabh_jaiswal.
</script>
4.5
Complejidad de tiempo: O(n) bajo el supuesto de que la búsqueda de unordered_map funciona en tiempo O(1).