Dada una array arr[] que consta de N enteros positivos, la tarea es minimizar el elemento restante de la array que se puede obtener eliminando repetidamente un par de elementos de la array y reemplazándolos por su diferencia absoluta.
Ejemplos:
Entrada: arr[] ={ 2, 7, 4, 1, 8, 1 }
Salida: 1
Explicación:
Quitar el par (arr[0], arr[2]) de arr[] e insertar abs(arr[0] – arr[2]) en arr[] modifica arr[] a { 2, 7, 1, 8, 1 }.
Quitar el par (arr[1], arr[3]) de arr[] e insertar abs(arr[1] – arr[3]) en arr[] modifica arr[] a { 2, 1, 1, 1 } .
Quitar el par (arr[0], arr[1]) de arr[] e insertar abs(arr[0] – arr[1]) en arr[] modifica arr[] a { 1, 1, 1 }.
Quitar el par (arr[0], arr[1]) de arr[] modifica arr[] a { 1 }.
Por lo tanto, la salida requerida es 1.Entrada: arr[] = { 1, 1, 4, 2, 2 }
Salida: 0
Enfoque: El problema se puede resolver usando programación dinámica basada en las siguientes observaciones:
Considere una array arr[] = { a, b, c, d }.
Si a > b, al eliminar el par (a, b) se modifica arr[] a { a – b, c, d }
Si c > d, al eliminar el par (c, d) se modifica arr[] a { a – b, c – d }
Si (a – b) > (c – d), entonces eliminando el par (a – b, c – d) modifica arr[] a { (a + d) – (b + c) }
De la observación anterior, se puede observar que el problema es dividir la array en dos subconjuntos con una diferencia mínima de las sumas de sus subconjuntos .
La siguiente es la relación de recurrencia:
min_diff(i, sum) = min(min_diff(i – 1, sum + arr[i – 1]), min_diff(i – 1, sum))
donde, i : índice de los elementos del arreglo
sum : suma de los elementos del primero subconjunto
Siga los pasos a continuación para resolver el problema:
- Inicialice una array 2D , digamos dp[][] , para almacenar la diferencia mínima de sumas de subconjuntos que se pueden obtener hasta el i -ésimo elemento.
- Utilice la relación de recurrencia anterior y calcule el valor de dp[N][sum] .
- Finalmente, imprima el valor de dp[N][suma] como la suma requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the smallest element
// left in the array by the given operations
int smallestLeft(int arr[], int total,
int sum, int i, vector<vector<int> > &dp)
{
// Base Case
if (i == 0) {
return abs(total - 2 * sum);
}
// If this subproblem
// has occurred previously
if (dp[i][sum] != -1)
return dp[i][sum];
// Including i-th array element
// into the first subset
int X = smallestLeft(arr, total,
sum + arr[i - 1], i - 1, dp);
// If i-th array element is not selected
int Y = smallestLeft(arr, total,
sum, i - 1, dp);
// Update dp[i][sum]
return dp[i][sum] = min(X, Y);
}
// Utility function to find smallest element
// left in the array by the given operations
int UtilSmallestElement(int arr[], int N)
{
// Stores sum of
// the array elements
int total = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
// Update total
total += arr[i];
}
// Stores overlapping
// subproblems
vector<vector<int> > dp(N + 1,
vector<int>(total, -1));
cout<< smallestLeft(arr, total,
0, N, dp);
}
// Driver Code
int main()
{
int arr[] = { 2, 7, 4, 1, 8, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
UtilSmallestElement(arr, N);
return 0;
}
Java
// Java program for above approach
import java.util.*;
import java.lang.*;
class GFG
{
// Function to find the smallest element
// left in the array by the given operations
static int smallestLeft(int arr[], int total,
int sum, int i, int[][] dp)
{
// Base Case
if (i == 0)
{
return Math.abs(total - 2 * sum);
}
// If this subproblem
// has occurred previously
if (dp[i][sum] != -1)
return dp[i][sum];
// Including i-th array element
// into the first subset
int X = smallestLeft(arr, total,
sum + arr[i - 1], i - 1, dp);
// If i-th array element is not selected
int Y = smallestLeft(arr, total,
sum, i - 1, dp);
// Update dp[i][sum]
return dp[i][sum] = Math.min(X, Y);
}
// Utility function to find smallest element
// left in the array by the given operations
static void UtilSmallestElement(int arr[], int N)
{
// Stores sum of
// the array elements
int total = 0;
// Traverse the array
for (int i = 0; i < N; i++)
{
// Update total
total += arr[i];
}
// Stores overlapping
// subproblems
int[][] dp = new int[N + 1][total];
for(int[] k:dp)
Arrays.fill(k, -1);
System.out.println(smallestLeft(arr, total,
0, N, dp));
}
// Driver function
public static void main (String[] args)
{
int arr[] = { 2, 7, 4, 1, 8, 1 };
int N = arr.length;
UtilSmallestElement(arr, N);
}
}
// This code is contributed by offbeat
Python3
# Python program to implement # the above approach # function to find the smallest element # left in the array by the given operations def smallestLeft( arr, total, sum, i, dp): # Base Case if (i == 0): return abs(total - 2 * sum) # If this subproblem # has occurred previously if (dp[i][sum] != -1): return dp[i][sum] # Including i-th array element # into the first subset X = smallestLeft(arr, total, sum + arr[i - 1], i - 1, dp) # If i-th array element is not selected Y = smallestLeft(arr, total, sum, i - 1, dp) # Update dp[i][sum] dp[i][sum] = min(X, Y) return dp[i][sum] # Utility function to find smallest element # left in the array by the given operations def UtilSmallestElement(arr, N): # Stores sum of # the array elements total = 0 # Traverse the array for i in range (0, N): # Update total total += arr[i] # Stores overlapping # subproblems dp = [[-1 for y in range(total)] for x in range(N+1)] print(smallestLeft(arr, total, 0, N, dp)) # Driver Code arr = [2, 7, 4, 1, 8, 1 ] N = len(arr) UtilSmallestElement(arr, N) # This code is contributed by amreshkumar3.
C#
// C# program for above approach
using System;
public class GFG
{
// Function to find the smallest element
// left in the array by the given operations
static int smallestLeft(int []arr, int total,
int sum, int i, int[,] dp)
{
// Base Case
if (i == 0)
{
return Math.Abs(total - 2 * sum);
}
// If this subproblem
// has occurred previously
if (dp[i,sum] != -1)
return dp[i,sum];
// Including i-th array element
// into the first subset
int X = smallestLeft(arr, total,
sum + arr[i - 1], i - 1, dp);
// If i-th array element is not selected
int Y = smallestLeft(arr, total,
sum, i - 1, dp);
// Update dp[i,sum]
return dp[i,sum] = Math.Min(X, Y);
}
// Utility function to find smallest element
// left in the array by the given operations
static void UtilSmallestElement(int []arr, int N)
{
// Stores sum of
// the array elements
int total = 0;
// Traverse the array
for (int i = 0; i < N; i++)
{
// Update total
total += arr[i];
}
// Stores overlapping
// subproblems
int[,] dp = new int[N + 1,total];
for(int i = 0; i < N + 1; i++)
{
for (int j = 0; j < total; j++)
{
dp[i, j] = -1;
}
}
Console.WriteLine(smallestLeft(arr, total,
0, N, dp));
}
// Driver function
public static void Main(String[] args)
{
int []arr = { 2, 7, 4, 1, 8, 1 };
int N = arr.Length;
UtilSmallestElement(arr, N);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// javascript program of the above approach
let M = 6;
let N = 7;
// Function to find the smallest element
// left in the array by the given operations
function smallestLeft(arr, total,
sum, i, dp)
{
// Base Case
if (i == 0)
{
return Math.abs(total - 2 * sum);
}
// If this subproblem
// has occurred previously
if (dp[i][sum] != -1)
return dp[i][sum];
// Including i-th array element
// into the first subset
let X = smallestLeft(arr, total,
sum + arr[i - 1], i - 1, dp);
// If i-th array element is not selected
let Y = smallestLeft(arr, total,
sum, i - 1, dp);
// Update dp[i][sum]
return dp[i][sum] = Math.min(X, Y);
}
// Utility function to find smallest element
// left in the array by the given operations
function UtilSmallestElement(arr, N)
{
// Stores sum of
// the array elements
let total = 0;
// Traverse the array
for (let i = 0; i < N; i++)
{
// Update total
total += arr[i];
}
// Stores overlapping
// subproblems
let dp = new Array(N + 1);
// Loop to create 2D array using 1D array
for (var i = 0; i < dp.length; i++) {
dp[i] = new Array(2);
}
for (var i = 0; i < dp.length; i++) {
for (var j = 0; j < dp.length; j++) {
dp[i][j] = 1;
}
}
document.write(smallestLeft(arr, total,
0, N, dp));
}
// Driver Code
let arr = [ 2, 7, 4, 1, 8, 1 ];
let n = arr.length;
UtilSmallestElement(arr, n);
// This code is contributed by target_2.
</script>
Producción:
1
Complejidad de tiempo: O(N * sum), donde sum es la suma de los elementos del arreglo
Espacio auxiliar: O(N * sum)
Enfoque de espacio optimizado: Para optimizar el enfoque anterior, la idea es utilizar el método de tabulación . Siga los pasos a continuación para resolver el problema:
- Inicialice una array , digamos dp[] , donde dp[i] verifica si la suma i se puede obtener como la suma de un subconjunto de la array dada.
- Recorra la array y calcule la suma de los elementos de la array y guárdela en una variable, digamos totalSum .
- Usando la relación de recurrencia anterior, encuentre el valor más cercano de (totalSum] / 2) , digamos X , tal que dp[X] sea verdadero.
- Finalmente, imprima el valor de (totalSum – 2 * X) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find minimize the remaining
// array element by removing pairs and
// replacing them by their absolute difference
int SmallestElementLeft(int arr[], int N)
{
// Stores sum of array elements
int totalSum = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
// Update totalSum
totalSum += arr[i];
}
// Stores half of totalSum
int req = totalSum / 2;
// dp[i]: True if sum i can be
// obtained as a subset sum
bool dp[req + 1];
// Initialize dp[] array
memset(dp, false, sizeof(dp));
// Base case
dp[0] = true;
// Stores closest sum that can
// be obtained as a subset sum
int reach = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
// Iterate over all possible value of sum
for (int j = req; j - arr[i] >= 0; j--) {
// Update dp[j]
dp[j] = dp[j] || dp[j - arr[i]];
// If sum i can be obtained
// from array elements
if (dp[j]) {
// Update reach
reach = max(reach, j);
}
}
}
return totalSum - (2 * reach);
}
// Driver Code
int main()
{
int arr[] = { 2, 2, 2 };
int N = sizeof(arr) / sizeof(arr[0]);
cout<< SmallestElementLeft(arr, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to find minimize the remaining
// array element by removing pairs and
// replacing them by their absolute difference
static int SmallestElementLeft(int arr[], int N)
{
// Stores sum of array elements
int totalSum = 0;
// Traverse the array
for(int i = 0; i < N; i++)
{
// Update totalSum
totalSum += arr[i];
}
// Stores half of totalSum
int req = totalSum / 2;
// dp[i]: True if sum i can be
// obtained as a subset sum
boolean[] dp = new boolean[req + 1];
// Initialize dp[] array
Arrays.fill(dp, false);
// Base case
dp[0] = true;
// Stores closest sum that can
// be obtained as a subset sum
int reach = 0;
// Traverse the array
for(int i = 0; i < N; i++)
{
// Iterate over all possible value of sum
for(int j = req; j - arr[i] >= 0; j--)
{
// Update dp[j]
dp[j] = dp[j] || dp[j - arr[i]];
// If sum i can be obtained
// from array elements
if (dp[j])
{
// Update reach
reach = Math.max(reach, j);
}
}
}
return totalSum - (2 * reach);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 2, 2 };
int N = arr.length;
System.out.print(SmallestElementLeft(arr, N));
}
}
// This code is contributed by code_hunt
Python3
# Python3 program to implement # the above approach # Function to find minimize the remaining # array element by removing pairs and # replacing them by their absolute difference def SmallestElementLeft(arr, N): # Stores sum of array elements totalSum = 0 # Traverse the array for i in range(N): # Update totalSum totalSum += arr[i] # Stores half of totalSum req = totalSum // 2 # dp[i]: True if sum i can be # obtained as a subset sum dp = [False for i in range(req + 1)] # Initialize dp[] array # memset(dp, false, sizeof(dp)); # Base case dp[0] = True # Stores closest sum that can # be obtained as a subset sum reach = 0 # Traverse the array for i in range(N): # Iterate over all possible value of sum j = req while j>=arr[i]: # Update dp[j] dp[j] = dp[j] or dp[j - arr[i]] # If sum i can be obtained # from array elements if (dp[j]): # Update reach reach = max(reach, j) j -= 1 return totalSum - (2 * reach) # Driver Code if __name__ == '__main__': arr = [2, 2, 2] N = len(arr) print(SmallestElementLeft(arr, N)) # This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function to find minimize the remaining
// array element by removing pairs and
// replacing them by their absolute difference
static int SmallestElementLeft(int[] arr, int N)
{
// Stores sum of array elements
int totalSum = 0;
// Traverse the array
for(int i = 0; i < N; i++)
{
// Update totalSum
totalSum += arr[i];
}
// Stores half of totalSum
int req = totalSum / 2;
// dp[i]: True if sum i can be
// obtained as a subset sum
bool[] dp = new bool[req + 1];
// Initialize dp[] array
for(int i = 0; i < req + 1; i++)
{
dp[i] = false;
}
// Base case
dp[0] = true;
// Stores closest sum that can
// be obtained as a subset sum
int reach = 0;
// Traverse the array
for(int i = 0; i < N; i++)
{
// Iterate over all possible value of sum
for(int j = req; j - arr[i] >= 0; j--)
{
// Update dp[j]
dp[j] = dp[j] || dp[j - arr[i]];
// If sum i can be obtained
// from array elements
if (dp[j])
{
// Update reach
reach = Math.Max(reach, j);
}
}
}
return totalSum - (2 * reach);
}
// Driver Code
public static void Main()
{
int[] arr = { 2, 2, 2 };
int N = arr.Length;
Console.Write(SmallestElementLeft(arr, N));
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to find minimize the remaining
// array element by removing pairs and
// replacing them by their absolute difference
function SmallestElementLeft(arr , N)
{
// Stores sum of array elements
var totalSum = 0;
// Traverse the array
for (i = 0; i < N; i++) {
// Update totalSum
totalSum += arr[i];
}
// Stores half of totalSum
var req = totalSum / 2;
// dp[i]: True if sum i can be
// obtained as a subset sum
var dp =Array(req + 1).fill(false);
// Base case
dp[0] = true;
// Stores closest sum that can
// be obtained as a subset sum
var reach = 0;
// Traverse the array
for (i = 0; i < N; i++) {
// Iterate over all possible value of sum
for (j = req; j - arr[i] >= 0; j--) {
// Update dp[j]
dp[j] = dp[j] || dp[j - arr[i]];
// If sum i can be obtained
// from array elements
if (dp[j]) {
// Update reach
reach = Math.max(reach, j);
}
}
}
return totalSum - (2 * reach);
}
// Driver Code
var arr = [ 2, 2, 2 ];
var N = arr.length;
document.write(SmallestElementLeft(arr, N));
// This code contributed by aashish1995
</script>
Producción:
2
Complejidad de tiempo: O(N * suma), donde suma es la suma de los elementos de la array
Espacio auxiliar: O(suma)
Publicación traducida automáticamente
Artículo escrito por 18bhupenderyadav18 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA