Pasos mínimos para hacer la suma y el producto de todos los elementos de la array distintos de cero

Dada una array arr de N enteros, la tarea es encontrar los pasos mínimos en los que la suma y el producto de todos los elementos de la array pueden hacerse distintos de cero. En un paso, cualquier elemento de la array se puede incrementar en 1.
Ejemplos: 
 

Entrada: N = 4, arr[] = {0, 1, 2, 3} 
Salida: 1 
Explicación: 
Como el producto de todos los elementos de la array es cero 
Incremente el elemento de la array 0 en 1, de modo que la suma y el producto de la array no sean igual a cero.
Entrada: N = 4, arr[] = {-1, -1, 0, 0} 
Salida: 3 
Explicación: 
Como el producto de todos los elementos de la array es cero 
Incremente el elemento de la array 2 y 3 en 1, de modo que la suma de la array y el producto no es igual a cero 
 

Enfoque: La idea es dividir el problema en dos partes, es decir: 
 

1. Pasos mínimos necesarios para que el producto de la array no sea igual a cero.
2. Pasos mínimos necesarios para que la suma de la array no sea igual a cero.

Para que el producto de todos los elementos de la array no sea igual a cero, entonces cada elemento de la array debe ser distinto de cero y para que la suma de la array no sea igual a cero, incremente cualquier elemento en 1 si la suma de la array es cero.
Por ejemplo: 
 

N = 4, arr[] = {0, 1, 2, 3}

Iterate over the array to find,
If there is an element that is zero.
If yes, then increment it by 1 and also
increment the number of steps by 1.

Again, Iterate over the updated array,
To check if the array sum is zero. 
If the array sum of the updated array
is zero then increment any element by 1. 

Algoritmo: 
 

• Itere sobre la array para verificar si hay un elemento que es cero, luego incremente el elemento en 1 y también incremente el número de pasos en 1
• Nuevamente, itere sobre la array y encuentre la suma de la array si la suma de la array es cero, luego incremente cualquier elemento en 1 y también incremente el número de pasos en 1.

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

// C++ implementation to find the
// minimum steps to make the array sum
// and the product not equal to zero
#include <bits/stdc++.h>
using namespace std;
 
int sum(int arr[], int n)
{
    int sum = 0;
    for(int i= 0; i < n; i++)
        sum += arr[i];
    return sum;
} 
 
// Function to to find the
// minimum steps to make the array sum
// and the product not equal to zero
int steps(int n, int a[])
{
      
    // Variable to store the minimum
    // number of steps required
    int count_steps = 0;
      
    // Loop to iterate over the array to
    // find if there is any element in
    // array which is zero
    for(int i = 0; i < n; i++)
    {
        if(a[i] == 0)
        {
            a[i] += 1;
            count_steps += 1;
        }
    }
      
    // Condition to check if the sum
    // of array elements is zero
    if( sum(a, n) != 0)
        return count_steps;
    else
        return count_steps + 1;
}
  
// Driver code
int main()
{
    int n = 4;
    int a[] = {-1, -1, 0, 0};
    int count = steps(n, a);
    cout<<(count);
    return 0;
}
 
// This code is contributed by Rajput-Ji

// Java implementation to find the
// minimum steps to make the array sum
// and the product not equal to zero
class GFG
{
     
// Function to to find the
// minimum steps to make the array sum
// and the product not equal to zero
static int steps(int n, int []a)
{
     
    // Variable to store the minimum
    // number of steps required
    int count_steps = 0;
     
    // Loop to iterate over the array to
    // find if there is any element in
    // array which is zero
    for(int i = 0; i < n; i++)
    {
        if(a[i] == 0)
        {
            a[i] += 1;
            count_steps += 1;
        }
    }
     
    // Condition to check if the sum
    // of array elements is zero
    if( sum(a) != 0)
        return count_steps;
    else
        return count_steps + 1;
}
 
static int sum(int[] arr)
{
    int sum = 0;
    for(int i= 0; i < arr.length; i++)
        sum += arr[i];
    return sum;
}
 
// Driver code
public static void main(String []args) {
    int n = 4;
    int []a = {-1, -1, 0, 0};
    int count = steps(n, a);
    System.out.println(count);
}
}
 
// This code is contributed by Rajput-Ji

# Python implementation to find the
# minimum steps to make the array sum
# and the product not equal to zero
 
# Function to to find the
# minimum steps to make the array sum
# and the product not equal to zero
def steps(n, a):
     
    # Variable to store the minimum
    # number of steps required
    count_steps = 0
     
    # Loop to iterate over the array to
    # find if there is any element in
    # array which is zero
    for i in range(n):
        if a[i]== 0:
            a[i] += 1
            count_steps += 1
     
    # Condition to check if the sum
    # of array elements is zero
    if sum(a)!= 0:
        return count_steps
    else:
        return count_steps + 1
 
# Driver code
if __name__ == "__main__":
    n = 4
    a = [-1, -1, 0, 0]
    count  = steps(n, a)
    print(count)

// C# implementation to find the
// minimum steps to make the array sum
// and the product not equal to zero
using System;
 
class GFG
{
     
// Function to to find the
// minimum steps to make the array sum
// and the product not equal to zero
static int steps(int n, int []a)
{
     
    // Variable to store the minimum
    // number of steps required
    int count_steps = 0;
     
    // Loop to iterate over the array to
    // find if there is any element in
    // array which is zero
    for(int i = 0; i < n; i++)
    {
        if(a[i] == 0)
        {
            a[i] += 1;
            count_steps += 1;
        }
    }
     
    // Condition to check if the sum
    // of array elements is zero
    if( sum(a) != 0)
        return count_steps;
    else
        return count_steps + 1;
}
 
static int sum(int[] arr)
{
    int sum = 0;
    for(int i= 0; i < arr.Length; i++)
        sum += arr[i];
    return sum;
}
 
// Driver code
public static void Main(String []args) {
    int n = 4;
    int []a = {-1, -1, 0, 0};
    int count = steps(n, a);
    Console.WriteLine(count);
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript implementation to find the
// minimum steps to make the array sum
// and the product not equal to zero
       
// Function to to find the
// minimum steps to make the array sum
// and the product not equal to zero
function steps(n, a)
{
       
    // Variable to store the minimum
    // number of steps required
    let count_steps = 0;
       
    // Loop to iterate over the array to
    // find if there is any element in
    // array which is zero
    for(let i = 0; i < n; i++)
    {
        if(a[i] == 0)
        {
            a[i] += 1;
            count_steps += 1;
        }
    }
       
    // Condition to check if the sum
    // of array elements is zero
    if( sum(a) != 0)
        return count_steps;
    else
        return count_steps + 1;
}
   
function sum(arr)
{
    let sum = 0;
    for(let i= 0; i < arr.length; i++)
        sum += arr[i];
    return sum;
}
 
// Driver Code
 
    let n = 4;
    let a = [-1, -1, 0, 0];
    let count = steps(n, a);
    document.write(count);
 
</script>

3

Análisis de rendimiento: 
 

• Complejidad de tiempo: en el enfoque dado, hay dos iteraciones para calcular los pasos mínimos necesarios para hacer que el producto sea distinto de cero y otra iteración para calcular la suma de la array. EN)
• Complejidad espacial: en el enfoque dado, no se utiliza espacio adicional. O(1)