Dada una array binaria ordenada en orden no creciente, cuente el número de 1 en ella.
Ejemplos:
C++
// C++ program to count one's in a boolean array
#include <bits/stdc++.h>
using namespace std;
/* Returns counts of 1's in arr[low..high]. The array is
assumed to be sorted in non-increasing order */
int countOnes(bool arr[], int low, int high)
{
if (high >= low)
{
// get the middle index
int mid = low + (high - low)/2;
// check if the element at middle index is last 1
if ( (mid == high || arr[mid+1] == 0) && (arr[mid] == 1))
return mid+1;
// If element is not last 1, recur for right side
if (arr[mid] == 1)
return countOnes(arr, (mid + 1), high);
// else recur for left side
return countOnes(arr, low, (mid -1));
}
return 0;
}
/* Driver Code */
int main()
{
bool arr[] = {1, 1, 1, 1, 0, 0, 0};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Count of 1's in given array is " << countOnes(arr, 0, n-1);
return 0;
}
Python3
# Python program to count one's in a boolean array
# Returns counts of 1's in arr[low..high]. The array is
# assumed to be sorted in non-increasing order
def countOnes(arr,low,high):
if high>=low:
# get the middle index
mid = low + (high-low)//2
# check if the element at middle index is last 1
if ((mid == high or arr[mid+1]==0) and (arr[mid]==1)):
return mid+1
# If element is not last 1, recur for right side
if arr[mid]==1:
return countOnes(arr, (mid+1), high)
# else recur for left side
return countOnes(arr, low, mid-1)
return 0
# Driver Code
arr=[1, 1, 1, 1, 0, 0, 0]
print ("Count of 1's in given array is",countOnes(arr, 0 , len(arr)-1))
# This code is contributed by __Devesh Agrawal__
Java
// Java program to count 1's in a sorted array
class CountOnes
{
/* Returns counts of 1's in arr[low..high]. The
array is assumed to be sorted in non-increasing
order */
int countOnes(int arr[], int low, int high)
{
if (high >= low)
{
// get the middle index
int mid = low + (high - low) / 2;
// check if the element at middle index is last
// 1
if ((mid == high || arr[mid + 1] == 0)
&& (arr[mid] == 1))
return mid + 1;
// If element is not last 1, recur for right
// side
if (arr[mid] == 1)
return countOnes(arr, (mid + 1), high);
// else recur for left side
return countOnes(arr, low, (mid - 1));
}
return 0;
}
/* Driver code */
public static void main(String args[])
{
CountOnes ob = new CountOnes();
int arr[] = { 1, 1, 1, 1, 0, 0, 0 };
int n = arr.length;
System.out.println("Count of 1's in given array is "
+ ob.countOnes(arr, 0, n - 1));
}
}
/* This code is contributed by Rajat Mishra */
C#
// C# program to count 1's in a sorted array
using System;
class GFG {
/* Returns counts of 1's in arr[low..high].
The array is assumed to be sorted in
non-increasing order */
static int countOnes(int[] arr, int low, int high)
{
if (high >= low)
{
// get the middle index
int mid = low + (high - low) / 2;
// check if the element at middle
// index is last 1
if ((mid == high || arr[mid + 1] == 0)
&& (arr[mid] == 1))
return mid + 1;
// If element is not last 1, recur
// for right side
if (arr[mid] == 1)
return countOnes(arr, (mid + 1), high);
// else recur for left side
return countOnes(arr, low, (mid - 1));
}
return 0;
}
/* Driver code */
public static void Main()
{
int[] arr = { 1, 1, 1, 1, 0, 0, 0 };
int n = arr.Length;
Console.WriteLine("Count of 1's in given "
+ "array is "
+ countOnes(arr, 0, n - 1));
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to count one's in a
// boolean array
/* Returns counts of 1's in arr[low..high].
The array is assumed to be sorted in
non-increasing order */
function countOnes( $arr, $low, $high)
{
if ($high >= $low)
{
// get the middle index
$mid = $low + ($high - $low)/2;
// check if the element at middle
// index is last 1
if ( ($mid == $high or $arr[$mid+1] == 0)
and ($arr[$mid] == 1))
return $mid+1;
// If element is not last 1, recur for
// right side
if ($arr[$mid] == 1)
return countOnes($arr, ($mid + 1),
$high);
// else recur for left side
return countOnes($arr, $low, ($mid -1));
}
return 0;
}
/* Driver code */
$arr = array(1, 1, 1, 1, 0, 0, 0);
$n = count($arr);
echo "Count of 1's in given array is " ,
countOnes($arr, 0, $n-1);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to count one's in a boolean array
/* Returns counts of 1's in arr[low..high]. The array is
assumed to be sorted in non-increasing order */
function countOnes( arr, low, high)
{
if (high >= low)
{
// get the middle index
let mid = Math.trunc(low + (high - low)/2);
// check if the element at middle index is last 1
if ( (mid == high || arr[mid+1] == 0) && (arr[mid] == 1))
return mid+1;
// If element is not last 1, recur for right side
if (arr[mid] == 1)
return countOnes(arr, (mid + 1), high);
// else recur for left side
return countOnes(arr, low, (mid -1));
}
return 0;
}
// Driver program
let arr = [ 1, 1, 1, 1, 0, 0, 0 ];
let n = arr.length;
document.write("Count of 1's in given array is " +
countOnes(arr, 0, n-1));
</script>
C++
#include <bits/stdc++.h>
using namespace std;
/* Returns counts of 1's in arr[low..high]. The array is
assumed to be sorted in non-increasing order */
int countOnes(bool arr[], int n)
{
int ans;
int low = 0, high = n - 1;
while (low <= high) { // get the middle index
int mid = (low + high) / 2;
// else recur for left side
if (arr[mid] < 1)
high = mid - 1;
// If element is not last 1, recur for right side
else if (arr[mid] > 1)
low = mid + 1;
else
// check if the element at middle index is last 1
{
if (mid == n - 1 || arr[mid + 1] != 1)
return mid + 1;
else
low = mid + 1;
}
}
}
int main()
{
bool arr[] = { 1, 1, 1, 1, 0, 0, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Count of 1's in given array is "
<< countOnes(arr, n);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG
{
static int countOnes(int arr[], int n)
{
int ans;
int low = 0, high = n - 1;
while (low <= high) { // get the middle index
int mid = (low + high) / 2;
// else recur for left side
if (arr[mid] < 1)
high = mid - 1;
// If element is not last 1, recur for right side
else if (arr[mid] > 1)
low = mid + 1;
else
// check if the element at middle index is last 1
{
if (mid == n - 1 || arr[mid + 1] != 1)
return mid + 1;
else
low = mid + 1;
}
}
return 0;
}
// Driver code
public static void main (String[] args) {
int arr[] = { 1, 1, 1, 1, 0, 0, 0 };
int n = arr.length;
System.out.println("Count of 1's in given array is "+ countOnes(arr, n));
}
}
// This code is contributed by patel2127.
Python3
'''package whatever #do not write package name here '''
def countOnes(arr, n):
low = 0;
high = n - 1;
while (low <= high): # get the middle index
mid = (low + high) // 2;
# else recur for left side
if (arr[mid] < 1):
high = mid - 1;
# If element is not last 1, recur for right side
elif(arr[mid] > 1):
low = mid + 1;
else:
# check if the element at middle index is last 1
if (mid == n - 1 or arr[mid + 1] != 1):
return mid + 1;
else:
low = mid + 1;
return 0;
# Driver code
if __name__ == '__main__':
arr = [ 1, 1, 1, 1, 0, 0, 0 ];
n = len(arr);
print("Count of 1's in given array is " , countOnes(arr, n));
# This code is contributed by umadevi9616
C#
/*package whatever //do not write package name here */
using System;
public class GFG {
static int countOnes(int []arr, int n) {
int low = 0, high = n - 1;
while (low <= high) { // get the middle index
int mid = (low + high) / 2;
// else recur for left side
if (arr[mid] < 1)
high = mid - 1;
// If element is not last 1, recur for right side
else if (arr[mid] > 1)
low = mid + 1;
else
// check if the element at middle index is last 1
{
if (mid == n - 1 || arr[mid + 1] != 1)
return mid + 1;
else
low = mid + 1;
}
}
return 0;
}
// Driver code
public static void Main(String[] args) {
int []arr = { 1, 1, 1, 1, 0, 0, 0 };
int n = arr.Length;
Console.WriteLine("Count of 1's in given array is " + countOnes(arr, n));
}
}
// This code is contributed by umadevi9616
Javascript
<script>
/* Returns counts of 1's in arr[low..high]. The array is
assumed to be sorted in non-increasing order */
function countOnes(arr,n)
{
let ans;
let low = 0, high = n - 1;
while (low <= high) { // get the middle index
let mid = Math.floor((low + high) / 2);
// else recur for left side
if (arr[mid] < 1)
high = mid - 1;
// If element is not last 1, recur for right side
else if (arr[mid] > 1)
low = mid + 1;
else
// check if the element at middle index is last 1
{
if (mid == n - 1 || arr[mid + 1] != 1)
return mid + 1;
else
low = mid + 1;
}
}
}
let arr=[ 1, 1, 1, 1, 0, 0, 0];
let n = arr.length;
document.write( "Count of 1's in given array is "+ countOnes(arr, n));
// This code is contributed by unknown2108
</script>
C++
#include <bits/stdc++.h>
using namespace std;
int main()
{
int arr[] = { 1, 1, 1, 1, 0, 0, 0, 0, 0 };
int size = sizeof(arr) / sizeof(arr[0]);
// Pointer to the first occurrence of zero
auto ptr
= upper_bound(arr, arr + size, 1, greater<int>());
cout << "Count of 1's in given array is " << (ptr - arr);
return 0;
}
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