Dada una array de elementos positivos, debe cambiar el signo de algunos de sus elementos de modo que la suma resultante de los elementos de la array sea mínima no negativa (lo más cerca posible de cero). Devuelve el número mínimo. de elementos cuyo signo debe invertirse de modo que la suma resultante sea mínima no negativa. Tenga en cuenta que la suma de todos los elementos de la array no excederá de 10 4 .
Ejemplos:
Entrada: arr[] = {15, 10, 6}
Salida: 1
Aquí, invertiremos el signo de 15
y la suma resultante será 1.
Entrada: arr[] = [14, 10, 4]
Salida: 1
Aquí , invertiremos el signo de 14 y la suma resultante será 0.
Tenga en cuenta que invertir los signos de 10 y 4 también da
como resultado la suma de 0, pero el recuento de elementos invertidos no es mínimo.
Enfoque ingenuo: Para cada elemento A[i], 0 ≤ i < n de la array, tenemos 2 opciones.
- El signo de A[i] se invierte (-ve).
- El signo de A[i] no se invierte (+ve).
Entonces podemos tener un total de 2 n configuraciones posibles de la array. Podemos mantener la suma de elementos y el número de lanzamientos en cada configuración y llevar un registro de la suma mínima (los empates se rompen por el número mínimo de lanzamientos). El número de lanzamientos en la configuración de suma mínima será la respuesta.
Complejidad de tiempo: O(2 n ) donde n es el número de elementos en la array.
Enfoque eficiente: este problema se puede resolver mediante programación dinámica y es una variación del problema estándar de la mochila 0/1. La diferencia es que tenemos 2 opciones allí, es decir, incluir un artículo en la mochila o excluirlo y aquí es como cambiar el signo del elemento o no. En lugar del peso de la bolsa en el problema de la mochila, aquí es la suma de todos los elementos de la array sin voltear (que es un máximo de 10 4 dado en el enunciado del problema).
Subestructura Óptima: Sea dp[i][j] el número mínimo de vueltas requeridas en los primeros i elementos de la array para hacer que la suma sea igual a j.
1 ≤ i ≤ n y -sum ≤ j ≤ sum donde sum es la suma de todos los elementos de la array sin voltear.
Si el signo de ar[i – 1] no se invierte para hacer sum = j
dp[i][j] = dp[i – 1][j – A[i – 1]]
Si el signo de ar[i – 1] se voltea para hacer sum = j
dp[i][j] = min(dp[i][j], dp[i – 1][j + A[i – 1]]+1)
Nota: dado que la suma de los elementos de la array podría ser negativa después de voltear. Entonces no podemos usar una array 2D para la tabulación porque en dp[i][j], j es la suma y los índices de la array no pueden ser negativos. Por lo tanto, vamos a utilizar una serie de mapas Hash. El tamaño de la array será n + 1.
Subproblemas superpuestos: Al igual que el problema de la mochila 0/1, aquí hay subproblemas superpuestos. No necesitamos evaluar los resultados una y otra vez, sino que podemos almacenar los resultados de los subproblemas en una tabla.
Complejidad de tiempo: O(n * sum)
Espacio auxiliar: O(n * sum)
donde n es el número de elementos y sum es la suma de los elementos de la array sin voltear.
Optimización del espacio:Si observa más de cerca la subestructura óptima, dp[i][j] dependerá solo de dp[i – 1][j – A[i – 1]]/dp[i – 1][j + A[ i-1]]. Por lo tanto, hay participación de solo 2 filas i e i – 1. Por lo tanto, solo necesitamos 2 filas en lugar de n + 1.
Los siguientes son los cambios que necesitamos para optimizar el espacio.
- En lugar de tomar tamaño de array = n + 1, declare una array de tamaño = 2.
- Introduzca una variable booleana (por ejemplo, bandera) para alternar entre mapas. Podemos inicializar el mapa dp[0] y comenzar a llenar dp[1]. En la siguiente iteración, dp[0] es el mapa actual y dp[1] es el anterior. De esta forma, podremos seguir alternando entre los 2 mapas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the
// minimum number of elements
// whose sign must be flipped
// to get the positive
// sum of array elements as close
// to 0 as possible
int solve(int A[], int n)
{
// Array of unordered_map of size=2.
unordered_map<int, int> dp[2];
// boolean variable used for
// toggling between maps
bool flag = 1;
// Calculate the sum of all
// elements of the array
int sum = 0;
for (int i = 0; i < n; i++)
sum += A[i];
// Initializing first map(dp[0])
// with INT_MAX because
// for i=0, there are no elements
// in the array to flip
for (int i = -sum; i <= sum; i++)
dp[0][i] = INT_MAX;
// Base Case
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = -sum; j <= sum; j++) {
dp[flag][j] = INT_MAX;
if (j - A[i - 1] <= sum && j - A[i - 1] >= -sum)
dp[flag][j] = dp[flag ^ 1][j - A[i - 1]];
if (j + A[i - 1] <= sum && j + A[i - 1] >= -sum
&& dp[flag ^ 1][j + A[i - 1]] != INT_MAX)
dp[flag][j]
= min(dp[flag][j],
dp[flag ^ 1][j + A[i - 1]] + 1);
}
// For toggling
flag = flag ^ 1;
}
// Required sum is minimum non-negative
// So, we iterate from i=0 to sum and find
// the first i where dp[flag ^ 1][i] != INT_MAX
for (int i = 0; i <= sum; i++) {
if (dp[flag ^ 1][i] != INT_MAX)
return dp[flag ^ 1][i];
}
// In worst case we will flip max n-1 elements
return n - 1;
}
// Driver code
int main()
{
int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << solve(arr, n);
return 0;
}
Java
// Java implementation of
// the above approach:
class GFG {
// Function to return the
// minimum number of elements
// whose sign must be flipped
// to get the positive
// sum of array elements as close
// to 0 as possible
public static int solve(int[] A, int n)
{
int[][] dp = new int[2000][2000];
// boolean variable used for
// toggling between maps
int flag = 1;
// Calculate the sum of all
// elements of the array
int sum = 0;
for (int i = 0; i < n; i++)
sum += A[i];
// Initializing first map(dp[0])
// with INT_MAX because for i=0,
// there are no elements in the
// array to flip
for (int i = -sum; i <= sum; i++) {
try {
dp[0][i] = Integer.MAX_VALUE;
}
catch (Exception e) {
}
}
// Base Case
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= sum; j++) {
try {
dp[flag][j] = Integer.MAX_VALUE;
if (j - A[i - 1] <= sum
&& j - A[i - 1] >= -sum)
dp[flag][j]
= dp[flag ^ 1][j - A[i - 1]];
if (j + A[i - 1] <= sum
&& j + A[i - 1] >= -sum
&& dp[flag ^ 1][j + A[i - 1]]
!= Integer.MAX_VALUE)
dp[flag][j] = Math.min(
dp[flag][j],
dp[flag ^ 1][j + A[i - 1]] + 1);
}
catch (Exception e) {
}
}
// For toggling
flag = flag ^ 1;
}
// Required sum is minimum non-negative
// So, we iterate from i=0 to sum and find
// the first i where dp[flag ^ 1][i] != INT_MAX
for (int i = 0; i <= sum; i++) {
if (dp[flag ^ 1][i] != Integer.MAX_VALUE)
return dp[flag ^ 1][i];
}
// In worst case we will flip max n-1 elements
return n - 1;
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 10, 22, 9, 33, 21, 50, 41, 60 };
int n = arr.length;
System.out.println(solve(arr, n));
}
}
// This code is contributed by sanjeev2552
Python3
# Python3 implementation of the approach # Function to return the minimum # number of elements # whose sign must be flipped # to get the positive # sum of array elements as close # to 0 as possible def solve(A, n): dp = [[0 for i in range(2000)] for i in range(2000)] # boolean variable used for # toggling between maps flag = 1 # Calculate the sum of all # elements of the array sum = 0 for i in range(n): sum += A[i] # Initializing first map(dp[0]) # with INT_MAX because # for i=0, there are no elements # in the array to flip for i in range(-sum, sum+1): dp[0][i] = 10**9 # Base Case dp[0][0] = 0 for i in range(1, n+1): for j in range(-sum, sum+1): dp[flag][j] = 10**9 if (j - A[i - 1] <= sum and j - A[i - 1] >= -sum): dp[flag][j] = dp[flag ^ 1][j - A[i - 1]] if (j + A[i - 1] <= sum and j + A[i - 1] >= -sum and dp[flag ^ 1][j + A[i - 1]] != 10**9): dp[flag][j] = min(dp[flag][j], dp[flag ^ 1][j + A[i - 1]] + 1) # For toggling flag = flag ^ 1 # Required sum is minimum non-negative # So, we iterate from i=0 to sum and find # the first i where dp[flag ^ 1][i] != INT_MAX for i in range(sum+1): if (dp[flag ^ 1][i] != 10**9): return dp[flag ^ 1][i] # In worst case we will flip max n-1 elements return n - 1 # Driver code arr = [10, 22, 9, 33, 21, 50, 41, 60] n = len(arr) print(solve(arr, n)) # This code is contributed by mohit kumar 29
C#
// C# implementation of the above approach:
using System;
class GFG
{
// Function to return the minimum number
// of elements whose sign must be flipped
// to get the positive sum of array elements
// as close to 0 as possible
public static int solve(int[] A, int n)
{
int[,] dp = new int[2000, 2000];
// boolean variable used for
// toggling between maps
int flag = 1;
// Calculate the sum of all elements
// of the array
int sum = 0;
for (int i = 0; i < n; i++)
sum += A[i];
// Initializing first map(dp[0]) with
// INT_MAX because for i=0, there are
// no elements in the array to flip
for (int i = -sum; i <= sum; i++)
{
try
{
dp[0, i] = int.MaxValue;
}
catch (Exception e){}
}
// Base Case
dp[0, 0] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= sum; j++)
{
try
{
dp[flag, j] = int.MaxValue;
if (j - A[i - 1] <= sum &&
j - A[i - 1] >= -sum)
dp[flag, j] = dp[flag ^ 1,
j - A[i - 1]];
if (j + A[i - 1] <= sum &&
j + A[i - 1] >= -sum &&
dp[flag ^ 1,
j + A[i - 1]] != int.MaxValue)
dp[flag, j] = Math.Min(dp[flag, j],
dp[flag ^ 1,
j + A[i - 1]] + 1);
} catch (Exception e) {}
}
// For toggling
flag = flag ^ 1;
}
// Required sum is minimum non-negative
// So, we iterate from i=0 to sum and find
// the first i where dp[flag ^ 1,i] != INT_MAX
for (int i = 0; i <= sum; i++)
{
if (dp[flag ^ 1, i] != int.MaxValue)
return dp[flag ^ 1, i];
}
// In worst case we will flip
// max n-1 elements
return n - 1;
}
// Driver code
public static void Main(String[] args)
{
int[] arr = { 10, 22, 9, 33,
21, 50, 41, 60 };
int n = arr.Length;
Console.WriteLine(solve(arr, n));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JS implementation of the approach
// Function to return the
// minimum number of elements
// whose sign must be flipped
// to get the positive
// sum of array elements as close
// to 0 as possible
function solve(A, n)
{
// Array of unordered_map of size=2.
let dp = [],
H = 2000, // 4 rows
W = 2000; // of 6 cells
for ( var y = 0; y < H; y++ ) {
dp[ y ] = [];
for ( var x = 0; x < W; x++ ) {
dp[ y ][ x ] = 0;
}
}
// boolean variable used for
// toggling between maps
let flag = 1;
// Calculate the sum of all
// elements of the array
let sum = 0;
for (let i = 0; i < n; i++)
sum += A[i];
// Initializing first map(dp[0])
// with INT_MAX because
// for i=0, there are no elements
// in the array to flip
for (let i = -sum; i <= sum; i++)
dp[0][i] = Number.MAX_VALUE;
// Base Case
dp[0][0] = 0;
for (let i = 1; i <= n; i++) {
for (let j = -sum; j <= sum; j++) {
dp[flag][j] = Number.MAX_VALUE;
if (j - A[i - 1] <= sum && j - A[i - 1] >= -sum)
dp[flag][j] = dp[flag ^ 1][j - A[i - 1]];
if (j + A[i - 1] <= sum && j + A[i - 1] >= -sum
&& dp[flag ^ 1][j + A[i - 1]] != Number.MAX_VALUE)
dp[flag][j]
= Math.min(dp[flag][j],
dp[flag ^ 1][j + A[i - 1]] + 1);
}
// For toggling
flag = flag ^ 1;
}
// Required sum is minimum non-negative
// So, we iterate from i=0 to sum and find
// the first i where dp[flag ^ 1][i] != MAX_VALUE
for (let i = 0; i <= sum; i++) {
if (dp[flag ^ 1][i] != Number.MAX_VALUE)
return dp[flag ^ 1][i];
}
// In worst case we will flip max n-1 elements
return n - 1;
}
// Driver code
let arr = [ 10, 22, 9, 33, 21, 50, 41, 60 ];
let n = arr.length;
document.write(solve(arr, n));
// This code is contributed by rohitsingh07052.
</script>
3
Complejidad temporal: O(n * suma).
Espacio auxiliar: O (suma) donde n es el número de elementos y la suma es la suma de los elementos de la array sin invertir.
Publicación traducida automáticamente
Artículo escrito por anmoldhawan1305 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA