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