Operaciones mínimas de incremento/decremento requeridas en Array para satisfacer las condiciones dadas

Dada una array arr[] de tamaño N , la tarea es encontrar el número mínimo de operaciones de incremento o decremento requeridas en cualquier índice i tal que para cada i (1 ≤ i < N) si la suma de elementos en el índice de 1 a i es positivo entonces la suma de los elementos de 1 a i + 1 debe ser negativa o viceversa.

Nota: Considere la array como una indexación basada en 1.

Ejemplos:

Entrada: arr[] = {3, -4, 5, 0, 1}
Salida: 6
Explicación: 
Convierta la array como {3, -4, 5, -5, 2}. Aquí, la suma de elementos hasta i se representa como si _.
Para i = 1, s ₁ = 3 y s ₂ = 3 + (-4) = -1. s ₁ es positivo y s ₂ es negativo.
Para i=2, s ₂ = -1 y s ₃ = 3 + (-4) + 5 = 4. s ₂ es negativo y s ₃ es positivo.
Para i = 3, s ₃ = 4 y s ₄ = 3 + (-4) + 5 + (-5) = -1. s ₃ es positivo y s ₄ es negativo.
Para i = 4, s₄ = -1 y s ₅ = 3 + (-4) + 5 +(-5) + 2 = 1. s ₄ es negativo y s ₅ es positivo.

Entrada: arr[] = {1, -2, 2, -3}
Salida: 0
Explicación: 
la array dada ya cumple la condición. Por lo tanto, no es necesario realizar ninguna operación. 

Enfoque: La array satisfará las condiciones si para cada i de 1 a N – 1 :

• Si i es impar , entonces la suma de los elementos de 1 a i es positiva .
• Si i es par , entonces la suma de los elementos de 1 a i es negativa y viceversa.

Pruebe las dos posibilidades anteriores y elija la que ofrezca el mínimo número de operaciones. A continuación se muestran los pasos:

1. Inicialice una variable num_of_ops = 0 que marca el número de operaciones realizadas hasta el momento.
2. Para cualquier índice i , si i es par y la suma de los elementos de 1 a ii es negativa , entonces agregue (1+|sum|) en el arr[i] para que sea positivo . Ahora la suma de los elementos de 1 a i será 1 . También agregue (1+|sum|) en num_of_ops, es decir, para contar el número de operaciones.
3. Si i es impar y la suma de los elementos de 1 a i es positiva , resta (1+|sum|) de a[i] para que sea negativa . Ahora la suma de los elementos de 1 a i será -1. También agregue (1+|sum|) en num_of_ops. es decir, para contar el número de operaciones.
4. De manera similar, encuentre el número de operaciones que se realizan para par i, la suma de elementos hasta que i sea negativa y para i impar la suma de elementos hasta que i sea positiva.
5. Elija el número mínimo de operaciones de los dos procedimientos anteriores.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <iostream>
using namespace std;
 
// Function to find minimum number
// of operations to get desired array
int minOperations(int a[], int N)
{
    int num_of_ops1, num_of_ops2, sum;
    num_of_ops1 = num_of_ops2 = sum = 0;
 
    // For even 'i', sum of
    // elements till 'i' is negative
 
    // For odd 'i', sum of
    // elements till 'i' is positive
    for (int i = 0; i < N; i++) {
        sum += a[i];
 
        // If i is even and sum is positive,
        // make it negative by subtracting
        // 1 + |s| from a[i]
        if (i % 2 == 0 && sum >= 0) {
            num_of_ops1 += (1 + abs(sum));
            sum = -1;
        }
 
        // If i is odd and sum is negative,
        // make it positive by
        // adding 1 + |s| into a[i]
        else if (i % 2 == 1 && sum <= 0) {
            num_of_ops1 += (1 + abs(sum));
            sum = 1;
        }
    }
 
    sum = 0;
 
    // For even 'i', the sum of
    // elements till 'i' is positive
 
    // For odd 'i', sum of
    // elements till 'i' is negative
    for (int i = 0; i < N; i++) {
        sum += a[i];
 
        // Check if 'i' is odd and sum is
        // positive, make it negative by
        // subtracting  1 + |s| from a[i]
        if (i % 2 == 1 && sum >= 0) {
            num_of_ops2 += (1 + abs(sum));
            sum = -1;
        }
 
        // Check if 'i' is even and sum
        // is negative, make it positive
        // by adding 1 + |s| into a[i]
        else if (i % 2 == 0 && sum <= 0) {
            num_of_ops2 += (1 + abs(sum));
            sum = 1;
        }
    }
 
    // Return the minimum of the two
    return min(num_of_ops1, num_of_ops2);
}
 
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 3, -4, 5, 0, 1 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    cout << minOperations(arr, N);
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG{
 
// Function to find minimum number
// of operations to get desired array
static int minOperations(int a[], int N)
{
    int num_of_ops1, num_of_ops2, sum;
    num_of_ops1 = num_of_ops2 = sum = 0;
 
    // For even 'i', sum of
    // elements till 'i' is negative
 
    // For odd 'i', sum of
    // elements till 'i' is positive
    for (int i = 0; i < N; i++)
    {
        sum += a[i];
 
        // If i is even and sum is positive,
        // make it negative by subtracting
        // 1 + |s| from a[i]
        if (i % 2 == 0 && sum >= 0)
        {
            num_of_ops1 += (1 + Math.abs(sum));
            sum = -1;
        }
 
        // If i is odd and sum is negative,
        // make it positive by
        // adding 1 + |s| into a[i]
        else if (i % 2 == 1 && sum <= 0)
        {
            num_of_ops1 += (1 + Math.abs(sum));
            sum = 1;
        }
    }
 
    sum = 0;
 
    // For even 'i', the sum of
    // elements till 'i' is positive
 
    // For odd 'i', sum of
    // elements till 'i' is negative
    for (int i = 0; i < N; i++)
    {
        sum += a[i];
 
        // Check if 'i' is odd and sum is
        // positive, make it negative by
        // subtracting  1 + |s| from a[i]
        if (i % 2 == 1 && sum >= 0)
        {
            num_of_ops2 += (1 + Math.abs(sum));
            sum = -1;
        }
 
        // Check if 'i' is even and sum
        // is negative, make it positive
        // by adding 1 + |s| into a[i]
        else if (i % 2 == 0 && sum <= 0)
        {
            num_of_ops2 += (1 + Math.abs(sum));
            sum = 1;
        }
    }
 
    // Return the minimum of the two
    return Math.min(num_of_ops1, num_of_ops2);
}
 
// Driver Code
public static void main(String[] args)
{
    // Given array arr[]
    int arr[] = { 3, -4, 5, 0, 1 };
    int N = arr.length;
 
    // Function Call
    System.out.print(minOperations(arr, N));
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program for the above approach
 
# Function to find minimum number
# of operations to get desired array
def minOperations(a, N):
 
    num_of_ops1 = num_of_ops2 = sum = 0;
 
    # For even 'i', sum of
    # elements till 'i' is negative
 
    # For odd 'i', sum of
    # elements till 'i' is positive
    for i in range(N):
        sum += a[i]
 
        # If i is even and sum is positive,
        # make it negative by subtracting
        # 1 + |s| from a[i]
        if (i % 2 == 0 and sum >= 0):
            num_of_ops1 += (1 + abs(sum))
            sum = -1
 
        # If i is odd and sum is negative,
        # make it positive by
        # adding 1 + |s| into a[i]
        elif (i % 2 == 1 and sum <= 0):
            num_of_ops1 += (1 + abs(sum))
            sum = 1
 
    sum = 0
 
    # For even 'i', the sum of
    # elements till 'i' is positive
 
    # For odd 'i', sum of
    # elements till 'i' is negative
    for i in range (N):
        sum += a[i]
 
        # Check if 'i' is odd and sum is
        # positive, make it negative by
        # subtracting 1 + |s| from a[i]
        if (i % 2 == 1 and sum >= 0):
            num_of_ops2 += (1 + abs(sum))
            sum = -1
 
        # Check if 'i' is even and sum
        # is negative, make it positive
        # by adding 1 + |s| into a[i]
        elif (i % 2 == 0 and sum <= 0):
            num_of_ops2 += (1 + abs(sum))
            sum = 1
 
    # Return the minimum of the two
    return min(num_of_ops1, num_of_ops2)
 
# Driver Code
if __name__ == "__main__":
     
    # Given array arr[]
    arr = [ 3, -4, 5, 0, 1 ]
    N = len(arr)
 
    # Function call
    print(minOperations(arr, N))
 
# This code is contributed by chitranayal

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find minimum number
// of operations to get desired array
static int minOperations(int []a, int N)
{
    int num_of_ops1, num_of_ops2, sum;
    num_of_ops1 = num_of_ops2 = sum = 0;
 
    // For even 'i', sum of
    // elements till 'i' is negative
 
    // For odd 'i', sum of
    // elements till 'i' is positive
    for(int i = 0; i < N; i++)
    {
        sum += a[i];
 
        // If i is even and sum is positive,
        // make it negative by subtracting
        // 1 + |s| from a[i]
        if (i % 2 == 0 && sum >= 0)
        {
            num_of_ops1 += (1 + Math.Abs(sum));
            sum = -1;
        }
 
        // If i is odd and sum is negative,
        // make it positive by
        // adding 1 + |s| into a[i]
        else if (i % 2 == 1 && sum <= 0)
        {
            num_of_ops1 += (1 + Math.Abs(sum));
            sum = 1;
        }
    }
 
    sum = 0;
 
    // For even 'i', the sum of
    // elements till 'i' is positive
 
    // For odd 'i', sum of
    // elements till 'i' is negative
    for(int i = 0; i < N; i++)
    {
        sum += a[i];
 
        // Check if 'i' is odd and sum is
        // positive, make it negative by
        // subtracting 1 + |s| from a[i]
        if (i % 2 == 1 && sum >= 0)
        {
            num_of_ops2 += (1 + Math.Abs(sum));
            sum = -1;
        }
 
        // Check if 'i' is even and sum
        // is negative, make it positive
        // by adding 1 + |s| into a[i]
        else if (i % 2 == 0 && sum <= 0)
        {
            num_of_ops2 += (1 + Math.Abs(sum));
            sum = 1;
        }
    }
 
    // Return the minimum of the two
    return Math.Min(num_of_ops1, num_of_ops2);
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given array []arr
    int []arr = { 3, -4, 5, 0, 1 };
    int N = arr.Length;
 
    // Function call
    Console.Write(minOperations(arr, N));
}
}
 
// This code is contributed by PrinciRaj1992

<script>
 
// Javascript program for the above approach
 
// Function to find minimum number
// of operations to get desired array
function minOperations(a, N)
{
    var num_of_ops1, num_of_ops2, sum;
    num_of_ops1 = num_of_ops2 = sum = 0;
 
    // For even 'i', sum of
    // elements till 'i' is negative
 
    // For odd 'i', sum of
    // elements till 'i' is positive
    for(i = 0; i < N; i++)
    {
        sum += a[i];
 
        // If i is even and sum is positive,
        // make it negative by subtracting
        // 1 + |s| from a[i]
        if (i % 2 == 0 && sum >= 0)
        {
            num_of_ops1 += (1 + Math.abs(sum));
            sum = -1;
        }
 
        // If i is odd and sum is negative,
        // make it positive by
        // adding 1 + |s| into a[i]
        else if (i % 2 == 1 && sum <= 0)
        {
            num_of_ops1 += (1 + Math.abs(sum));
            sum = 1;
        }
    }
 
    sum = 0;
 
    // For even 'i', the sum of
    // elements till 'i' is positive
 
    // For odd 'i', sum of
    // elements till 'i' is negative
    for(i = 0; i < N; i++)
    {
        sum += a[i];
 
        // Check if 'i' is odd and sum is
        // positive, make it negative by
        // subtracting 1 + |s| from a[i]
        if (i % 2 == 1 && sum >= 0)
        {
            num_of_ops2 += (1 + Math.abs(sum));
            sum = -1;
        }
 
        // Check if 'i' is even and sum
        // is negative, make it positive
        // by adding 1 + |s| into a[i]
        else if (i % 2 == 0 && sum <= 0)
        {
            num_of_ops2 += (1 + Math.abs(sum));
            sum = 1;
        }
    }
 
    // Return the minimum of the two
    return Math.min(num_of_ops1, num_of_ops2);
}
 
// Driver Code
 
// Given array arr
var arr = [ 3, -4, 5, 0, 1 ];
var N = arr.length;
 
// Function Call
document.write(minOperations(arr, N));
 
// This code is contributed by aashish1995
 
</script>

6

Complejidad temporal: O(N)
Espacio auxiliar: O(1)