Minimice los elementos distintos de cero en el Array mediante una operación dada

Dada una array arr[] de longitud N , la tarea es minimizar el recuento del número de elementos distintos de cero sumando el valor del elemento actual a cualquiera de sus elementos adyacentes y restando del elemento actual como máximo una vez.
Ejemplos: 
 

Entrada: arr[] = { 1, 0, 1, 0, 0, 1 } 
Salida: 2 
Explicación:  
Operación 1: arr[0] -> arr[1], arr[] = {0, 1, 1, 0 , 0, 1} 
Operación 2: arr[2] -> arr[1], arr[] = {0, 2, 0, 0, 0, 1} 
Recuento de elementos distintos de cero = 2
Entrada: arr[] = { 1, 0, 1, 1, 1, 0, 1 } 
Salida: 3 
Explicación:  
Operación 1: arr[2] -> arr[3], arr[] = {1, 0, 0, 2, 1, 0 , 1} 
Operación 2: arr[4] -> arr[3], arr[] = {1, 0, 0, 3, 0, 0, 1} 
Recuento de elementos distintos de cero = 3 
 

Enfoque: La idea es usar algoritmos codiciosos para elegir con avidez en cada paso. La observación clave en el problema es que solo puede haber tres posibilidades de tres índices consecutivos i, j y k, es decir 
 

• Tanto el índice final tiene un elemento distinto de cero.
• Cualquiera de los índices tiene un elemento distinto de cero.

En los dos casos anteriores, siempre podemos sumar los valores al elemento central y restar a los elementos adyacentes. De manera similar, podemos elegir con avidez las operaciones y actualizar los elementos de la array para minimizar los elementos distintos de cero.
A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation to minimize the
// non-zero elements in the array
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to minimize the non-zero
// elements in the given array
int minOccupiedPosition(int A[], int n)
{
 
    // To store the min pos needed
    int minPos = 0;
 
    // Loop to iterate over the elements
    // of the given array
    for (int i = 0; i < n; ++i) {
 
        // If current position A[i] is occupied
        // the we can place A[i], A[i+1] and A[i+2]
        // elements together at A[i+1] if exists.
        if (A[i] > 0) {
            ++minPos;
            i += 2;
        }
    }
 
    return minPos;
}
 
// Driver Code
int main()
{
    int A[] = { 8, 0, 7, 0, 0, 6 };
    int n = sizeof(A) / sizeof(A[0]);
 
    // Function Call
    cout << minOccupiedPosition(A, n);
    return 0;
}

// Java implementation to minimize the
// non-zero elements in the array
 
class GFG{
 
// Function to minimize the non-zero
// elements in the given array
static int minOccupiedPosition(int A[], int n)
{
     
    // To store the min pos needed
    int minPos = 0;
 
    // Loop to iterate over the elements
    // of the given array
    for (int i = 0; i < n; ++i)
    {
 
        // If current position A[i] is occupied
        // the we can place A[i], A[i+1] and A[i+2]
        // elements together at A[i+1] if exists.
        if (A[i] > 0) {
            ++minPos;
            i += 2;
        }
    }
    return minPos;
}
 
// Driver Code
public static void main(String[] args)
{
    int A[] = { 8, 0, 7, 0, 0, 6 };
    int n = A.length;
 
    // Function Call
    System.out.print(minOccupiedPosition(A, n));
}
}
 
// This code is contributed by gauravrajput1

# Python3 implementation to minimize the
# non-zero elements in the array
 
# Function to minimize the non-zero
# elements in the given array
def minOccupiedPosition(A, n):
 
    # To store the min pos needed
    minPos = 0
 
    # Loop to iterate over the elements
    # of the given array
    i = 0
    while i < n:
 
        # If current position A[i] is
        # occupied the we can place A[i],
        # A[i+1] and A[i+2] elements
        # together at A[i+1] if exists.
        if(A[i] > 0):
 
            minPos += 1
            i += 2
        i += 1
         
    return minPos
 
# Driver Code
if __name__ == '__main__':
     
    A = [ 8, 0, 7, 0, 0, 6 ]
    n = len(A)
 
    # Function Call
    print(minOccupiedPosition(A, n))
     
# This code is contributed by Shivam Singh

// C# implementation to minimize the
// non-zero elements in the array
using System;
 
class GFG {
     
// Function to minimize the non-zero
// elements in the given array
static int minOccupiedPosition(int[] A, int n)
{
         
    // To store the min pos needed
    int minPos = 0;
     
    // Loop to iterate over the elements
    // of the given array
    for(int i = 0; i < n; ++i)
    {
         
       // If current position A[i] is occupied
       // the we can place A[i], A[i+1] and A[i+2]
       // elements together at A[i+1] if exists.
       if (A[i] > 0)
       {
           ++minPos;
           i += 2;
       }
    }
    return minPos;
}
 
// Driver code   
static void Main()
{
    int[] A = { 8, 0, 7, 0, 0, 6 };
    int n = A.Length;
 
    // Function Call
    Console.WriteLine(minOccupiedPosition(A, n));
}
}
 
// This code is contributed by divyeshrabadiya07

<script>
// Javascript implementation to minimize the
// non-zero elements in the array
 
// Function to minimize the non-zero
// elements in the given array
function minOccupiedPosition( A, n)
{
 
    // To store the min pos needed
    var minPos = 0;
 
    // Loop to iterate over the elements
    // of the given array
    for (var i = 0; i < n; ++i) {
 
        // If current position A[i] is occupied
        // the we can place A[i], A[i+1] and A[i+2]
        // elements together at A[i+1] if exists.
        if (A[i] > 0) {
            ++minPos;
            i += 2;
        }
    }
 
    return minPos;
}
 
 var A = [ 8, 0, 7, 0, 0, 6 ];
 var n = A.length;
 
    // Function Call
    document.write(minOccupiedPosition(A, n));
 
// This code is contributed by SoumikMondal
</script>

2

Complejidad temporal: O(N) .

Espacio Auxiliar: O(1)