Dada una array arr[] de N enteros, la tarea es encontrar el número mínimo de incrementos/decrementos de los elementos de la array en 1 para hacer que el signo del prefijo sume la alternancia de la array.
Ejemplos:
Entrada: arr[] = {1, -3, 1, 0}
Salida: 4
Explicación: Las
siguientes son las operaciones realizadas en los elementos de array dados:
- Incrementar el elemento de la array arr[1](= -3) en 1 modifica la array a {1, -2, 1, 0}.
- Incrementar el elemento de la array arr[2](= 1) en 1 modifica la array a {1, -2, 2, 0}.
- Decrementar el elemento de la array arr[3](= 0) en 1 modifica la array a {1, -2, 2, -1}.
- Decrementar el elemento de la array arr[3](= -1) en 1 modifica la array a {1, -2, 2, -2}.
Después de las operaciones anteriores, la suma del prefijo de la array modificada es {1, -1, 1, -1}, que está en un orden de signos alternativo. Por lo tanto, el número mínimo de operaciones requeridas es 4.
Entrada: arr[] = {3, -6, 4, -5, 7}
Salida: 0
Enfoque: El problema dado se puede resolver modificando el elemento de la array usando las operaciones dadas en el orden, es decir, positivo, negativo, positivo… o negativo, positivo, negativo,… e imprima el mínimo de las dos operaciones requeridas. Siga los pasos a continuación para resolver el problema dado:
- Para el Caso 1: modificando el elemento de la array en el orden de negativo, positivo, negativo:
- Inicialice las variables current_prefix_1 como 0 que almacena la suma del prefijo de la array.
- Inicialice las variables minOperationCase1 como 0 que almacena el número mínimo resultante de operaciones requeridas.
- Recorra la array dada y realice los siguientes pasos:
- Incremente el prefijo_actual_1 por arr[i] .
- Si el valor de current_prefix_1 o la paridad es -ve, incremente el número mínimo de operaciones en abs(parity – current_prefix_1) .
- Multiplica la paridad por (-1) .
- De manera similar, como se discutió en el Caso 1, encuentre el número mínimo de operaciones requeridas para el orden del prefijo sum como positivo, negativo, positivo, … y guárdelo en una variable minOperationCase2 .
- Después de completar los pasos anteriores, imprima el mínimo de minOperationCase1 y minOperationCase2 como las operaciones resultantes requeridas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum number
// of increments/decrements of array
// elements by 1 to make signs of
// prefix sum array elements alternating
int minimumOperations(int A[], int N)
{
// Case 1. neg - pos - neg
int cur_prefix_1 = 0;
// Stores the current sign of
// the prefix sum of array
int parity = -1;
// Stores minimum number of operations
// for Case 1
int minOperationsCase1 = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
cur_prefix_1 += A[i];
// Checking both conditions
if (cur_prefix_1 == 0
|| parity * cur_prefix_1 < 0) {
minOperationsCase1
+= abs(parity - cur_prefix_1);
// Update the current prefix1 to
// currentPrefixSum
cur_prefix_1 = parity;
}
parity *= -1;
}
// Case 2. pos - neg - pos
int cur_prefix_2 = 0;
// Stores the prefix sum of array
parity = 1;
// Stores minimum number of operations
// for Case 1
int minOperationsCase2 = 0;
for (int i = 0; i < N; i++) {
cur_prefix_2 += A[i];
// Checking both conditions
if (cur_prefix_2 == 0
|| parity * cur_prefix_2 < 0) {
minOperationsCase2
+= abs(parity - cur_prefix_2);
// Update the current prefix2 to
// currentPrefixSum
cur_prefix_2 = parity;
}
parity *= -1;
}
return min(minOperationsCase1,
minOperationsCase2);
}
// Driver Code
int main()
{
int A[] = { 1, -3, 1, 0 };
int N = sizeof(A) / sizeof(A[0]);
cout << minimumOperations(A, N);
return 0;
}
Java
// Java code for above approach
import java.util.*;
class GFG{
// Function to find the minimum number
// of increments/decrements of array
// elements by 1 to make signs of
// prefix sum array elements alternating
static int minimumOperations(int A[], int N)
{
// Case 1. neg - pos - neg
int cur_prefix_1 = 0;
// Stores the current sign of
// the prefix sum of array
int parity = -1;
// Stores minimum number of operations
// for Case 1
int minOperationsCase1 = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
cur_prefix_1 += A[i];
// Checking both conditions
if (cur_prefix_1 == 0
|| parity * cur_prefix_1 < 0) {
minOperationsCase1
+= Math.abs(parity - cur_prefix_1);
// Update the current prefix1 to
// currentPrefixSum
cur_prefix_1 = parity;
}
parity *= -1;
}
// Case 2. pos - neg - pos
int cur_prefix_2 = 0;
// Stores the prefix sum of array
parity = 1;
// Stores minimum number of operations
// for Case 1
int minOperationsCase2 = 0;
for (int i = 0; i < N; i++) {
cur_prefix_2 += A[i];
// Checking both conditions
if (cur_prefix_2 == 0
|| parity * cur_prefix_2 < 0) {
minOperationsCase2
+= Math.abs(parity - cur_prefix_2);
// Update the current prefix2 to
// currentPrefixSum
cur_prefix_2 = parity;
}
parity *= -1;
}
return Math.min(minOperationsCase1,
minOperationsCase2);
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 1, -3, 1, 0 };
int N = A.length;
System.out.print(minimumOperations(A, N));
}
}
// This code is contributed by avijitmondal1998.
Python3
# Python program for the above approach # Function to find the minimum number # of increments/decrements of array # elements by 1 to make signs of # prefix sum array elements alternating def minimumOperations(A, N) : # Case 1. neg - pos - neg cur_prefix_1 = 0 # Stores the current sign of # the prefix sum of array parity = -1 # Stores minimum number of operations # for Case 1 minOperationsCase1 = 0 # Traverse the array for i in range(N) : cur_prefix_1 += A[i] # Checking both conditions if (cur_prefix_1 == 0 or parity * cur_prefix_1 < 0) : minOperationsCase1 += abs(parity - cur_prefix_1) # Update the current prefix1 to # currentPrefixSum cur_prefix_1 = parity parity *= -1 # Case 2. pos - neg - pos cur_prefix_2 = 0 # Stores the prefix sum of array parity = 1 # Stores minimum number of operations # for Case 1 minOperationsCase2 = 0 for i in range(N) : cur_prefix_2 += A[i] # Checking both conditions if (cur_prefix_2 == 0 or parity * cur_prefix_2 < 0) : minOperationsCase2 += abs(parity - cur_prefix_2) # Update the current prefix2 to # currentPrefixSum cur_prefix_2 = parity parity *= -1 return min(minOperationsCase1, minOperationsCase2) # Driver Code A = [ 1, -3, 1, 0 ] N = len(A) print(minimumOperations(A, N)) # This code is contributed by splevel62.
C#
// C# code for above approach
using System;
public class GFG
{
// Function to find the minimum number
// of increments/decrements of array
// elements by 1 to make signs of
// prefix sum array elements alternating
static int minimumOperations(int []A, int N)
{
// Case 1. neg - pos - neg
int cur_prefix_1 = 0;
// Stores the current sign of
// the prefix sum of array
int parity = -1;
// Stores minimum number of operations
// for Case 1
int minOperationsCase1 = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
cur_prefix_1 += A[i];
// Checking both conditions
if (cur_prefix_1 == 0
|| parity * cur_prefix_1 < 0) {
minOperationsCase1
+= Math.Abs(parity - cur_prefix_1);
// Update the current prefix1 to
// currentPrefixSum
cur_prefix_1 = parity;
}
parity *= -1;
}
// Case 2. pos - neg - pos
int cur_prefix_2 = 0;
// Stores the prefix sum of array
parity = 1;
// Stores minimum number of operations
// for Case 1
int minOperationsCase2 = 0;
for (int i = 0; i < N; i++) {
cur_prefix_2 += A[i];
// Checking both conditions
if (cur_prefix_2 == 0
|| parity * cur_prefix_2 < 0) {
minOperationsCase2
+= Math.Abs(parity - cur_prefix_2);
// Update the current prefix2 to
// currentPrefixSum
cur_prefix_2 = parity;
}
parity *= -1;
}
return Math.Min(minOperationsCase1,
minOperationsCase2);
}
// Driver Code
public static void Main(String[] args)
{
int []A = { 1, -3, 1, 0 };
int N = A.Length;
Console.Write(minimumOperations(A, N));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program for the above approach
// Function to find the minimum number
// of increments/decrements of array
// elements by 1 to make signs of
// prefix sum array elements alternating
function minimumOperations(A, N)
{
// Case 1. neg - pos - neg
let cur_prefix_1 = 0;
// Stores the current sign of
// the prefix sum of array
let parity = -1;
// Stores minimum number of operations
// for Case 1
let minOperationsCase1 = 0;
// Traverse the array
for (let i = 0; i < N; i++) {
cur_prefix_1 += A[i];
// Checking both conditions
if (cur_prefix_1 == 0 || parity * cur_prefix_1 < 0) {
minOperationsCase1 += Math.abs(parity - cur_prefix_1);
// Update the current prefix1 to
// currentPrefixSum
cur_prefix_1 = parity;
}
parity *= -1;
}
// Case 2. pos - neg - pos
let cur_prefix_2 = 0;
// Stores the prefix sum of array
parity = 1;
// Stores minimum number of operations
// for Case 1
let minOperationsCase2 = 0;
for (let i = 0; i < N; i++) {
cur_prefix_2 += A[i];
// Checking both conditions
if (cur_prefix_2 == 0 || parity * cur_prefix_2 < 0) {
minOperationsCase2 += Math.abs(parity - cur_prefix_2);
// Update the current prefix2 to
// currentPrefixSum
cur_prefix_2 = parity;
}
parity *= -1;
}
return Math.min(minOperationsCase1, minOperationsCase2);
}
// Driver Code
let A = [1, -3, 1, 0];
let N = A.length;
document.write(minimumOperations(A, N));
// This code is contributed by _saurabh_jaiswal.
</script>
Producción:
4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA