Elimine todos los 1 de la izquierda adyacente de 0 en una array binaria

Dada una array binaria arr[] , la tarea es encontrar el número de operaciones necesarias para eliminar todos los 1 de la izquierda adyacente de los 0. En cada operación, todos los 1, inmediatamente a la izquierda de un 0, se cambian a 0.

Ejemplos:  

Entrada: arr[] = { 1, 0, 0, 1, 1, 0 } 
Salida: 2 
Explicación: 
Operación 1: Cambio en el índice 0 y 4. arr[] = { 0, 0, 0, 1, 0, 0 } 
Operación 2: Cambio en el índice 3. arr[] = { 0, 0, 0, 0, 0, 0 } 
No se requieren más operaciones.

Entrada: arr[] = { 0, 1, 0, 1 } 
Salida: 1 
Explicación: 
Operación 1: Cambio en el índice 1. arr[] = { 0, 0, 0, 1 } 
No se requieren más operaciones.  

Enfoque: este problema se puede resolver utilizando el enfoque codicioso . La idea es calcular la cantidad máxima de 1 consecutivos antes de 0 , lo que da la cantidad de veces que se necesita realizar la operación dada para que la array no pueda modificarse más.

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

// C++ implementation of the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum number
// of 1's before 0
void noOfMoves(int arr[], int n)
{
    int cnt = 0;
    int maxCnt = 0;
 
    // Traverse the array
    for (int i = 0; i < n; i++) {
 
        // If value is 1
        if (arr[i] == 1) {
            cnt++;
        }
        else {
 
            // If consecutive 1 followed
            // by 0, then update the maxCnt
            if (cnt != 0) {
                maxCnt = max(maxCnt, cnt);
                cnt = 0;
            }
        }
    }
 
    // Print the maximum consecutive 1's
    // followed by 0
    cout << maxCnt << endl;
}
 
// Driver Code
int main()
{
    int arr[] = { 0, 1, 1, 1, 1, 0,
                  0, 1, 1, 0, 0, 1 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    noOfMoves(arr, N);
    int arr1[] = { 1, 0, 1, 0, 1, 0, 1, 0 };
    N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    noOfMoves(arr1, N);
    return 0;
}

// Java implementation of the above approach
class GFG{
 
// Function to find the maximum number
// of 1's before 0
static void noOfMoves(int arr[], int n)
{
    int cnt = 0;
    int maxCnt = 0;
 
    // Traverse the array
    for (int i = 0; i < n; i++) {
 
        // If value is 1
        if (arr[i] == 1) {
            cnt++;
        }
        else {
 
            // If consecutive 1 followed
            // by 0, then update the maxCnt
            if (cnt != 0) {
                maxCnt = Math.max(maxCnt, cnt);
                cnt = 0;
            }
        }
    }
 
    // Print the maximum consecutive 1's
    // followed by 0
    System.out.print(maxCnt +"\n");
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 0, 1, 1, 1, 1, 0,
                0, 1, 1, 0, 0, 1 };
    int N = arr.length;
 
    // Function Call
    noOfMoves(arr, N);
    int arr1[] = { 1, 0, 1, 0, 1, 0, 1, 0 };
    N = arr1.length;
 
    // Function Call
    noOfMoves(arr1, N);
}
}
 
// This code is contributed by 29AjayKumar

# Python 3 implementation of the above approach
 
# Function to find the maximum number
# of 1's before 0
def noOfMoves(arr,n):
    cnt = 0
    maxCnt = 0
 
    # Traverse the array
    for i in range(n):
        # If value is 1
        if (arr[i] == 1):
            cnt += 1
        else:
            # If consecutive 1 followed
            # by 0, then update the maxCnt
            if (cnt != 0):
                maxCnt = max(maxCnt, cnt)
                cnt = 0
 
    # Print the maximum consecutive 1's
    # followed by 0
    print(maxCnt)
 
# Driver Code
if __name__ == '__main__':
    arr = [0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1]
    N = len(arr)
 
    # Function Call
    noOfMoves(arr, N)
    arr1 = [1, 0, 1, 0, 1, 0, 1, 0]
    N = len(arr1)
 
    # Function Call
    noOfMoves(arr1, N)
 
# This code is contributed by Surendra_Gangwar

// C# implementation of the above approach
using System;
 
public class GFG{
  
// Function to find the maximum number
// of 1's before 0
static void noOfMoves(int []arr, int n)
{
    int cnt = 0;
    int maxCnt = 0;
  
    // Traverse the array
    for (int i = 0; i < n; i++) {
  
        // If value is 1
        if (arr[i] == 1) {
            cnt++;
        }
        else {
  
            // If consecutive 1 followed
            // by 0, then update the maxCnt
            if (cnt != 0) {
                maxCnt = Math.Max(maxCnt, cnt);
                cnt = 0;
            }
        }
    }
  
    // Print the maximum consecutive 1's
    // followed by 0
    Console.Write(maxCnt +"\n");
}
  
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 0, 1, 1, 1, 1, 0,
                0, 1, 1, 0, 0, 1 };
    int N = arr.Length;
  
    // Function Call
    noOfMoves(arr, N);
    int []arr1 = { 1, 0, 1, 0, 1, 0, 1, 0 };
    N = arr1.Length;
  
    // Function Call
    noOfMoves(arr1, N);
}
}
 
// This code contributed by Rajput-Ji

<script>
 
// JavaScript implementation of the above approach
 
// Function to find the maximum number
// of 1's before 0
function noOfMoves(arr, n)
{
    let cnt = 0;
    let maxCnt = 0;
 
    // Traverse the array
    for (let i = 0; i < n; i++) {
 
        // If value is 1
        if (arr[i] == 1) {
            cnt++;
        }
        else {
 
            // If consecutive 1 followed
            // by 0, then update the maxCnt
            if (cnt != 0) {
                maxCnt = Math.max(maxCnt, cnt);
                cnt = 0;
            }
        }
    }
 
    // Print the maximum consecutive 1's
    // followed by 0
    document.write( maxCnt + "<br>");
}
 
// Driver Code
 
    let arr = [ 0, 1, 1, 1, 1, 0,
                0, 1, 1, 0, 0, 1 ];
    let N = arr.length;
 
    // Function Call
    noOfMoves(arr, N);
    let arr1 = [ 1, 0, 1, 0, 1, 0, 1, 0 ];
    N = arr.length;
 
    // Function Call
    noOfMoves(arr1, N);
 
//This code is contributed by Mayank Tyagi
</script>

4
1

Complejidad de tiempo: O(N) , donde N es la longitud de la array.