Encuentra el número de ceros – Part 1

Dada una array de 1 y 0 que tiene todos los 1 primero seguidos de todos los 0. Encuentre el número de 0s. Cuente el número de ceros en la array dada.
Ejemplos: 

Input: arr[] = {1, 1, 1, 1, 0, 0}
Output: 2

Input: arr[] = {1, 0, 0, 0, 0}
Output: 4

Input: arr[] = {0, 0, 0}
Output: 3

Input: arr[] = {1, 1, 1, 1}
Output: 0

Enfoque 1: una solución simple es atravesar la array de entrada. Tan pronto como encontramos un 0, devolvemos n – índice del primer 0. Aquí n es el número de elementos en la array de entrada. La complejidad temporal de esta solución sería O(n).

La implementación del enfoque anterior se encuentra a continuación:

C++

#include <bits/stdc++.h>
using namespace std;
int firstzeroindex(int arr[], int n)
{
    for (int i = 0; i < n; i++) {
        if (arr[i] == 0) {
            return i;
        }
    }
    return -1;
}
int main()
{
    int arr[] = { 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = firstzeroindex(arr, n);
    if (x == -1) {
        cout << "Count of zero is 0" << endl;
    }
    else {
        cout << "count of zero is " << n - x << endl;
    }
    return 0;
}
// this code is contributed by machhaliya muhammad
Producción

count of zero is 6

Complejidad de tiempo: O(n) donde n es el tamaño de arr.

Enfoque 2: dado que la array de entrada está ordenada, podemos usar la búsqueda binaria para encontrar la primera aparición de 0. Una vez que tenemos el índice del primer elemento, podemos devolver la cuenta como n: índice del primer cero.

Implementación:

C

// A divide and conquer solution to find count of zeroes in an array
// where all 1s are present before all 0s
#include <stdio.h>
 
/* if 0 is present in arr[] then returns the index of FIRST occurrence
of 0 in arr[low..high], otherwise returns -1 */
int firstZero(int arr[], int low, int high)
{
    if (high >= low)
    {
        // Check if mid element is first 0
        int mid = low + (high - low)/2;
        if (( mid == 0 || arr[mid-1] == 1) && arr[mid] == 0)
            return mid;
 
        if (arr[mid] == 1) // If mid element is not 0
            return firstZero(arr, (mid + 1), high);
        else // If mid element is 0, but not first 0
            return firstZero(arr, low, (mid -1));
    }
    return -1;
}
 
// A wrapper over recursive function firstZero()
int countZeroes(int arr[], int n)
{
    // Find index of first zero in given array
    int first = firstZero(arr, 0, n-1);
 
    // If 0 is not present at all, return 0
    if (first == -1)
        return 0;
 
    return (n - first);
}
 
/* Driver program to check above functions */
int main()
{
    int arr[] = {1, 1, 1, 0, 0, 0, 0, 0};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("Count of zeroes is %d", countZeroes(arr, n));
    return 0;
}

C++

// A divide and conquer solution to
// find count of zeroes in an array
// where all 1s are present before all 0s
#include <bits/stdc++.h>
using namespace std;
 
/* if 0 is present in arr[] then
returns the index of FIRST occurrence
of 0 in arr[low..high], otherwise returns -1 */
int firstZero(int arr[], int low, int high)
{
    if (high >= low)
    {
        // Check if mid element is first 0
        int mid = low + (high - low) / 2;
        if ((mid == 0 || arr[mid - 1] == 1) &&
                         arr[mid] == 0)
            return mid;
 
        // If mid element is not 0
        if (arr[mid] == 1)
            return firstZero(arr, (mid + 1), high);
         
        // If mid element is 0, but not first 0   
        else
            return firstZero(arr, low, (mid -1));
    }
    return -1;
}
 
// A wrapper over recursive function firstZero()
int countZeroes(int arr[], int n)
{
    // Find index of first zero in given array
    int first = firstZero(arr, 0, n - 1);
 
    // If 0 is not present at all, return 0
    if (first == -1)
        return 0;
 
    return (n - first);
}
 
// Driver Code
int main()
{
    int arr[] = {1, 1, 1, 0, 0, 0, 0, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of zeroes is "
         << countZeroes(arr, n);
    return 0;
}
 
// This code is contributed by SoumikMondal

Java

// A divide and conquer solution to find count of zeroes in an array
// where all 1s are present before all 0s
 
class CountZeros
{
    /* if 0 is present in arr[] then returns the index of FIRST occurrence
       of 0 in arr[low..high], otherwise returns -1 */
    int firstZero(int arr[], int low, int high)
    {
        if (high >= low)
        {
            // Check if mid element is first 0
            int mid = low + (high - low) / 2;
            if ((mid == 0 || arr[mid - 1] == 1) && arr[mid] == 0)
                return mid;
 
            if (arr[mid] == 1) // If mid element is not 0
                return firstZero(arr, (mid + 1), high);
            else // If mid element is 0, but not first 0
                return firstZero(arr, low, (mid - 1));
        }
        return -1;
    }
 
    // A wrapper over recursive function firstZero()
    int countZeroes(int arr[], int n)
    {
        // Find index of first zero in given array
        int first = firstZero(arr, 0, n - 1);
 
        // If 0 is not present at all, return 0
        if (first == -1)
            return 0;
 
        return (n - first);
    }
 
    // Driver program to test above functions
    public static void main(String[] args)
    {
        CountZeros count = new CountZeros();
        int arr[] = {1, 1, 1, 0, 0, 0, 0, 0};
        int n = arr.length;
        System.out.println("Count of zeroes is " + count.countZeroes(arr, n));
    }
}

Python3

# A divide and conquer solution to
# find count of zeroes in an array
# where all 1s are present before all 0s
 
# if 0 is present in arr[] then returns
# the index of FIRST occurrence of 0 in
# arr[low..high], otherwise returns -1
def firstZero(arr, low, high):
 
    if (high >= low):
     
        # Check if mid element is first 0
        mid = low + int((high - low) / 2)
        if (( mid == 0 or arr[mid-1] == 1)
                      and arr[mid] == 0):
            return mid
         
        # If mid element is not 0
        if (arr[mid] == 1):
            return firstZero(arr, (mid + 1), high)
             
        # If mid element is 0, but not first 0
        else:
            return firstZero(arr, low, (mid - 1))
     
    return -1
 
# A wrapper over recursive
# function firstZero()
def countZeroes(arr, n):
 
    # Find index of first zero in given array
    first = firstZero(arr, 0, n - 1)
 
    # If 0 is not present at all, return 0
    if (first == -1):
        return 0
 
    return (n - first)
 
# Driver Code
arr = [1, 1, 1, 0, 0, 0, 0, 0]
n = len(arr)
print("Count of zeroes is",
        countZeroes(arr, n))
 
# This code is contributed by Smitha Dinesh Semwal

C#

// A divide and conquer solution to find
// count of zeroes in an array where all
// 1s are present before all 0s
using System;
 
class CountZeros
{
    /* if 0 is present in arr[] then returns
       the index of FIRST occurrence of 0 in
       arr[low..high], otherwise returns -1 */
    int firstZero(int []arr, int low, int high)
    {
        if (high >= low)
        {
            // Check if mid element is first 0
            int mid = low + (high - low) / 2;
            if ((mid == 0 || arr[mid - 1] == 1) &&
                                 arr[mid] == 0)
                return mid;
 
            if (arr[mid] == 1) // If mid element is not 0
                return firstZero(arr, (mid + 1), high);
                 
            else // If mid element is 0, but not first 0
                return firstZero(arr, low, (mid - 1));
        }
        return -1;
    }
 
    // A wrapper over recursive function firstZero()
    int countZeroes(int []arr, int n)
    {
        // Find index of first zero in given array
        int first = firstZero(arr, 0, n - 1);
 
        // If 0 is not present at all, return 0
        if (first == -1)
            return 0;
 
        return (n - first);
    }
 
    // Driver program to test above functions
    public static void Main()
    {
        CountZeros count = new CountZeros();
        int []arr = {1, 1, 1, 0, 0, 0, 0, 0};
        int n = arr.Length;
        Console.Write("Count of zeroes is " +
                       count.countZeroes(arr, n));
    }
}
 
// This code is contributed by nitin mittal.

PHP

<?php
// A divide and conquer solution to
// find count of zeroes in an array
// where all 1s are present before all 0s
 
/* if 0 is present in arr[] then
   returns the index of FIRST
   occurrence of 0 in arr[low..high],
   otherwise returns -1 */
function firstZero($arr, $low, $high)
{
    if ($high >= $low)
    {
         
        // Check if mid element is first 0
        $mid = $low + floor(($high - $low)/2);
         
        if (( $mid == 0 || $arr[$mid-1] == 1) &&
                                 $arr[$mid] == 0)
            return $mid;
 
        // If mid element is not 0
        if ($arr[$mid] == 1)
            return firstZero($arr, ($mid + 1), $high);
         
        // If mid element is 0,
        // but not first 0   
        else
            return firstZero($arr, $low,
                            ($mid - 1));
    }
    return -1;
}
 
// A wrapper over recursive
// function firstZero()
function countZeroes($arr, $n)
{
     
    // Find index of first
    // zero in given array
    $first = firstZero($arr, 0, $n - 1);
 
    // If 0 is not present
    // at all, return 0
    if ($first == -1)
        return 0;
 
    return ($n - $first);
}
     
    // Driver Code
    $arr = array(1, 1, 1, 0, 0, 0, 0, 0);
    $n = sizeof($arr);
    echo("Count of zeroes is ");
    echo(countZeroes($arr, $n));
     
// This code is contributed by nitin mittal
?>

Javascript

<script>
// A divide and conquer solution to find count of zeroes in an array
// where all 1s are present before all 0s
 
    /*
     * if 0 is present in arr then returns the index of FIRST occurrence of 0 in
     * arr[low..high], otherwise returns -1
     */
    function firstZero(arr , low , high) {
        if (high >= low) {
         
            // Check if mid element is first 0
            var mid = low + parseInt((high - low) / 2);
            if ((mid == 0 || arr[mid - 1] == 1) && arr[mid] == 0)
                return mid;
 
            if (arr[mid] == 1) // If mid element is not 0
                return firstZero(arr, (mid + 1), high);
            else // If mid element is 0, but not first 0
                return firstZero(arr, low, (mid - 1));
        }
        return -1;
    }
 
    // A wrapper over recursive function firstZero()
    function countZeroes(arr , n)
    {
     
        // Find index of first zero in given array
        var first = firstZero(arr, 0, n - 1);
 
        // If 0 is not present at all, return 0
        if (first == -1)
            return 0;
 
        return (n - first);
    }
 
    // Driver program to test above functions
 
        var arr = [ 1, 1, 1, 0, 0, 0, 0, 0 ];
        var n = arr.length;
        document.write("Count of zeroes is " + countZeroes(arr, n));
 
// This code is contributed by gauravrajput1
</script>
Producción

Count of zeroes is 5

Complejidad de tiempo: O(Logn) donde n es el número de elementos en arr[].

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *