Dado un entero positivo K y dos arreglos A[] y B[] que consisten en M y N enteros positivos del rango [1, K] respectivamente, la tarea es minimizar el recuento de reemplazos de elementos del arreglo por valores del rango [ 1, K] tal que la suma de los elementos de ambas arrays sea igual. Si es imposible hacer que la suma sea igual, imprima -1 .
Ejemplos:
Entrada: K = 6, A[] = {3, 4, 1}, B[] = {6, 6, 6}
Salida: 2
Explicación:
una de las formas posibles es reemplazar elementos de la array B[] en los índices 0 y 1 con 1 en dos movimientos. Por lo tanto, la array B[] se modifica a {1, 1, 6}.
Ahora, la suma de ambas arrays es 8, que es igual.Entrada: A[] = {4, 3, 2}, B[] = {2, 3, 3, 1}, K = 6, N = 4, M = 3
Salida: 0
Enfoque: El problema dado se puede resolver utilizando la técnica de dos puntos . Siga los pasos a continuación para resolver el problema:
- Inicialice 4 variables, digamos l1 = 0, r1 = M – 1, l2 = 0, r2 = N – 1 , que se utilizan para recorrer la array .
- Inicialice una variable, digamos res , para almacenar el recuento de reemplazos mínimos requeridos.
- Ordene ambas arrays dadas en orden ascendente .
- Encuentre la diferencia de la suma de ambas arrays y guárdela en una variable, digamos diff .
- Iterar hasta que l1 ≤ r1 o l2 ≤ r2 y realizar los siguientes pasos:
- Si diff = 0: salir del bucle .
- Si diff excede 0: Tome el máximo entre (A[r1] – 1) y (K – B[l2]) y réstelo de la diferencia diff y luego incremente l2 , si el valor de (K – B[l2]) es mayor. De lo contrario, disminuya r1 en uno.
- De lo contrario, tome el máximo entre (B[r2] – 1) y (K – A[l1]) y súmelo a la diferencia diff , luego incremente l1 , si (K – A[l1]) es mayor. De lo contrario, disminuya el valor de r2 en 1 .
- Incremente el valor de res en 1 .
- Después de completar los pasos anteriores, imprima el valor de res como el número mínimo de reemplazos de elementos de array requeridos.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum number
// of replacements required to make
// the sum of two arrays equal
int makeSumEqual(vector<int> a, vector<int> b,
int K, int M, int N)
{
// Stores the sum of a[]
int sum1 = 0;
// Stores the sum of b[]
int sum2 = 0;
// Calculate sum of the array a[]
for (int el : a)
sum1 += el;
// Calculate sum of the array b[]
for (int el : b)
sum2 += el;
// Stores the difference
// between a[] and b[]
int diff = sum1 - sum2;
// Left and Right pointer
// to traverse the array a[]
int l1 = 0, r1 = M - 1;
// Left and Right pointer
// to traverse the array b[]
int l2 = 0, r2 = N - 1;
// Stores the count of moves
int res = 0;
// Sort the arrays in
// ascending order
sort(a.begin(),a.end());
sort(b.begin(),b.end());
// Iterate while diff != 0 and
// l1 <= r1 or l2 <= r2
while (l1 <= r1 || l2 <= r2)
{
if (diff == 0)
{
break;
}
// If diff is greater than 0
if (diff > 0)
{
// If all pointers are valid
if (l2 <= r2 && l1 <= r1)
{
if (K - b[l2] < a[r1] - 1) {
int sub = min(
a[r1] - 1, diff);
diff -= sub;
a[r1] -= sub;
r1--;
}
else {
int sub = min(
K - b[l2], diff);
diff -= sub;
b[l2] += sub;
l2++;
}
}
// Otherwise, if only pointers
// of array a[] is valid
else if (l1 <= r1) {
int sub = min(
a[r1] - 1, diff);
diff -= sub;
a[r1] -= sub;
r1--;
}
// Otherwise
else {
int sub = min(
K - b[l2], diff);
diff -= sub;
b[l2] += sub;
l2++;
}
}
// If diff is less than 0
else {
// If all pointers are valid
if (l1 <= r1 && l2 <= r2) {
if (K - a[l1]
< b[r2] - 1) {
int sub = min(
b[r2] - 1,
-1 * diff);
diff += sub;
b[r2] -= sub;
r2--;
}
else {
int sub = min(
K - a[l1],
-1 * diff);
diff += sub;
a[l1] -= sub;
l1++;
}
}
// Otherwise, if only pointers
// of array a[] is valid
else if (l2 <= r2) {
int sub
= min(
b[r2] - 1,
-1 * diff);
diff += sub;
b[r2] -= sub;
r2--;
}
// Otherwise
else {
int sub = min(
K - a[l1], diff);
diff += sub;
a[l1] += sub;
l1++;
}
}
// Increment count
// of res by one
res++;
}
// If diff is 0, then return res
if (diff == 0)
return res;
// Otherwise, return -1
else
return -1;
}
// Driver Code
int main()
{
vector<int> A = { 1, 4, 3 };
vector<int> B = { 6, 6, 6 };
int M = A.size();
int N = B.size();
int K = 6;
cout << makeSumEqual(A, B, K,M, N);
return 0;
}
// This code is contributed by mohit kumar 29.
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find minimum number
// of replacements required to make
// the sum of two arrays equal
public static int makeSumEqual(
int[] a, int[] b, int K,
int M, int N)
{
// Stores the sum of a[]
int sum1 = 0;
// Stores the sum of b[]
int sum2 = 0;
// Calculate sum of the array a[]
for (int el : a)
sum1 += el;
// Calculate sum of the array b[]
for (int el : b)
sum2 += el;
// Stores the difference
// between a[] and b[]
int diff = sum1 - sum2;
// Left and Right pointer
// to traverse the array a[]
int l1 = 0, r1 = M - 1;
// Left and Right pointer
// to traverse the array b[]
int l2 = 0, r2 = N - 1;
// Stores the count of moves
int res = 0;
// Sort the arrays in
// ascending order
Arrays.sort(a);
Arrays.sort(b);
// Iterate while diff != 0 and
// l1 <= r1 or l2 <= r2
while (l1 <= r1 || l2 <= r2) {
if (diff == 0) {
break;
}
// If diff is greater than 0
if (diff > 0) {
// If all pointers are valid
if (l2 <= r2 && l1 <= r1) {
if (K - b[l2] < a[r1] - 1) {
int sub = Math.min(
a[r1] - 1, diff);
diff -= sub;
a[r1] -= sub;
r1--;
}
else {
int sub = Math.min(
K - b[l2], diff);
diff -= sub;
b[l2] += sub;
l2++;
}
}
// Otherwise, if only pointers
// of array a[] is valid
else if (l1 <= r1) {
int sub = Math.min(
a[r1] - 1, diff);
diff -= sub;
a[r1] -= sub;
r1--;
}
// Otherwise
else {
int sub = Math.min(
K - b[l2], diff);
diff -= sub;
b[l2] += sub;
l2++;
}
}
// If diff is less than 0
else {
// If all pointers are valid
if (l1 <= r1 && l2 <= r2) {
if (K - a[l1]
< b[r2] - 1) {
int sub = Math.min(
b[r2] - 1,
-1 * diff);
diff += sub;
b[r2] -= sub;
r2--;
}
else {
int sub = Math.min(
K - a[l1],
-1 * diff);
diff += sub;
a[l1] -= sub;
l1++;
}
}
// Otherwise, if only pointers
// of array a[] is valid
else if (l2 <= r2) {
int sub
= Math.min(
b[r2] - 1,
-1 * diff);
diff += sub;
b[r2] -= sub;
r2--;
}
// Otherwise
else {
int sub = Math.min(
K - a[l1], diff);
diff += sub;
a[l1] += sub;
l1++;
}
}
// Increment count
// of res by one
res++;
}
// If diff is 0, then return res
if (diff == 0)
return res;
// Otherwise, return -1
else
return -1;
}
// Driver Code
public static void main(String[] args)
{
int[] A = { 1, 4, 3 };
int[] B = { 6, 6, 6 };
int M = A.length;
int N = B.length;
int K = 6;
System.out.println(
makeSumEqual(A, B, K,
M, N));
}
}
Python3
# Python program for the above approach # Function to find minimum number # of replacements required to make # the sum of two arrays equal from functools import cmp_to_key def cmp(c, d): return c - d def makeSumEqual(a, b, K, M, N): # Stores the sum of a[] sum1 = 0 # Stores the sum of b[] sum2 = 0 # Calculate sum of the array a[] for el in range(len(a)): sum1 += a[el] # Calculate sum of the array b[] for el in range(len(b)): sum2 += b[el] # Stores the difference # between a[] and b[] diff = sum1 - sum2 # Left and Right pointer # to traverse the array a[] l1 = 0 r1 = M - 1 # Left and Right pointer # to traverse the array b[] l2 = 0 r2 = N - 1 # Stores the count of moves res = 0 # Sort the arrays in # ascending order a.sort(key=cmp_to_key(cmp)) b.sort(key=cmp_to_key(cmp)) # Iterate while diff != 0 and # l1 <= r1 or l2 <= r2 while(l1 <= r1 or l2 <= r2): if (diff == 0): break # If diff is greater than 0 if(diff > 0): # If all pointers are valid if(l2 <= r2 and l1 <= r1): if(K - b[l2] < a[r1] - 1): sub = min(a[r1] - 1, diff) diff -= sub a[r1] -= sub r1 -= 1 else: sub = min(K - b[l2], diff) diff -= sub b[l2] += sub l2 += 1 # Otherwise, if only pointers # of array a[] is valid elif(l1 <= r1): sub = min(a[r1] - 1, diff) diff -= sub a[r1] -= sub r1 -= 1 # Otherwise else: sub = min(K - b[l2], diff) diff -= sub b[l2] += sub l2 += 1 # If diff is less than 0 else: # If all pointers are valid if(l1 <= r1 and l2 <= r2): if (K - a[l1]< b[r2] - 1): sub = min(b[r2] - 1,-1 * diff) diff += sub b[r2] -= sub r2 -= 1 else: sub = min(K - a[l1],-1 * diff) diff += sub a[l1] -= sub l1 += 1 # Otherwise, if only pointers # of array a[] is valid elif(l2 <= r2): sub = min(b[r2] - 1,-1 * diff) diff += sub b[r2] -= sub r2 -= 1 # Otherwise else: sub = min(K - a[l1], diff) diff += sub a[l1] += sub l1 += 1 # Increment count # of res by one res += 1 # If diff is 0, then return res if (diff == 0): return res # Otherwise, return -1 else: return -1 # Driver Code A=[1, 4, 3 ] B=[6, 6, 6 ] M = len(A) N = len(B) K = 6 print(makeSumEqual(A, B, K,M, N)) # This code is contributed by shinjanpatra
C#
// C# program to implement
// the above approach
using System;
public class GFG
{
// Function to find minimum number
// of replacements required to make
// the sum of two arrays equal
public static int makeSumEqual(
int[] a, int[] b, int K,
int M, int N)
{
// Stores the sum of a[]
int sum1 = 0;
// Stores the sum of b[]
int sum2 = 0;
// Calculate sum of the array a[]
foreach (int el in a)
sum1 += el;
// Calculate sum of the array b[]
foreach (int el in b)
sum2 += el;
// Stores the difference
// between a[] and b[]
int diff = sum1 - sum2;
// Left and Right pointer
// to traverse the array a[]
int l1 = 0, r1 = M - 1;
// Left and Right pointer
// to traverse the array b[]
int l2 = 0, r2 = N - 1;
// Stores the count of moves
int res = 0;
// Sort the arrays in
// ascending order
Array.Sort(a);
Array.Sort(b);
// Iterate while diff != 0 and
// l1 <= r1 or l2 <= r2
while (l1 <= r1 || l2 <= r2) {
if (diff == 0) {
break;
}
// If diff is greater than 0
if (diff > 0) {
// If all pointers are valid
if (l2 <= r2 && l1 <= r1) {
if (K - b[l2] < a[r1] - 1) {
int sub = Math.Min(
a[r1] - 1, diff);
diff -= sub;
a[r1] -= sub;
r1--;
}
else {
int sub = Math.Min(
K - b[l2], diff);
diff -= sub;
b[l2] += sub;
l2++;
}
}
// Otherwise, if only pointers
// of array a[] is valid
else if (l1 <= r1) {
int sub = Math.Min(
a[r1] - 1, diff);
diff -= sub;
a[r1] -= sub;
r1--;
}
// Otherwise
else {
int sub = Math.Min(
K - b[l2], diff);
diff -= sub;
b[l2] += sub;
l2++;
}
}
// If diff is less than 0
else {
// If all pointers are valid
if (l1 <= r1 && l2 <= r2) {
if (K - a[l1]
< b[r2] - 1) {
int sub = Math.Min(
b[r2] - 1,
-1 * diff);
diff += sub;
b[r2] -= sub;
r2--;
}
else {
int sub = Math.Min(
K - a[l1],
-1 * diff);
diff += sub;
a[l1] -= sub;
l1++;
}
}
// Otherwise, if only pointers
// of array a[] is valid
else if (l2 <= r2) {
int sub
= Math.Min(
b[r2] - 1,
-1 * diff);
diff += sub;
b[r2] -= sub;
r2--;
}
// Otherwise
else {
int sub = Math.Min(
K - a[l1], diff);
diff += sub;
a[l1] += sub;
l1++;
}
}
// Increment count
// of res by one
res++;
}
// If diff is 0, then return res
if (diff == 0)
return res;
// Otherwise, return -1
else
return -1;
}
// Driver Code
public static void Main(String[] args)
{
int[] A = { 1, 4, 3 };
int[] B = { 6, 6, 6 };
int M = A.Length;
int N = B.Length;
int K = 6;
Console.WriteLine(
makeSumEqual(A, B, K,
M, N));
}
}
Javascript
<script>
// Javascript program for the above approach
// Function to find minimum number
// of replacements required to make
// the sum of two arrays equal
function makeSumEqual(a,b,K,M,N)
{
// Stores the sum of a[]
let sum1 = 0;
// Stores the sum of b[]
let sum2 = 0;
// Calculate sum of the array a[]
for (let el=0;el< a.length;el++)
sum1 += a[el];
// Calculate sum of the array b[]
for (let el=0;el< b.length;el++)
sum2 += b[el];
// Stores the difference
// between a[] and b[]
let diff = sum1 - sum2;
// Left and Right pointer
// to traverse the array a[]
let l1 = 0, r1 = M - 1;
// Left and Right pointer
// to traverse the array b[]
let l2 = 0, r2 = N - 1;
// Stores the count of moves
let res = 0;
// Sort the arrays in
// ascending order
a.sort(function(c,d){return c-d;});
b.sort(function(c,d){return c-d;});
// Iterate while diff != 0 and
// l1 <= r1 or l2 <= r2
while (l1 <= r1 || l2 <= r2) {
if (diff == 0) {
break;
}
// If diff is greater than 0
if (diff > 0) {
// If all pointers are valid
if (l2 <= r2 && l1 <= r1) {
if (K - b[l2] < a[r1] - 1) {
let sub = Math.min(
a[r1] - 1, diff);
diff -= sub;
a[r1] -= sub;
r1--;
}
else {
let sub = Math.min(
K - b[l2], diff);
diff -= sub;
b[l2] += sub;
l2++;
}
}
// Otherwise, if only pointers
// of array a[] is valid
else if (l1 <= r1) {
let sub = Math.min(
a[r1] - 1, diff);
diff -= sub;
a[r1] -= sub;
r1--;
}
// Otherwise
else {
let sub = Math.min(
K - b[l2], diff);
diff -= sub;
b[l2] += sub;
l2++;
}
}
// If diff is less than 0
else {
// If all pointers are valid
if (l1 <= r1 && l2 <= r2) {
if (K - a[l1]
< b[r2] - 1) {
let sub = Math.min(
b[r2] - 1,
-1 * diff);
diff += sub;
b[r2] -= sub;
r2--;
}
else {
let sub = Math.min(
K - a[l1],
-1 * diff);
diff += sub;
a[l1] -= sub;
l1++;
}
}
// Otherwise, if only pointers
// of array a[] is valid
else if (l2 <= r2) {
let sub
= Math.min(
b[r2] - 1,
-1 * diff);
diff += sub;
b[r2] -= sub;
r2--;
}
// Otherwise
else {
let sub = Math.min(
K - a[l1], diff);
diff += sub;
a[l1] += sub;
l1++;
}
}
// Increment count
// of res by one
res++;
}
// If diff is 0, then return res
if (diff == 0)
return res;
// Otherwise, return -1
else
return -1;
}
// Driver Code
let A=[1, 4, 3 ];
let B=[6, 6, 6 ];
let M = A.length;
let N = B.length;
let K = 6;
document.write(makeSumEqual(A, B, K,
M, N));
// This code is contributed by unknown2108
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)