Count 1’s in a sorted binary array
Given a binary array arr[] of size N, which is sorted in non-increasing order, count the number of 1’s in it.
Examples:
Input: arr[] = {1, 1, 0, 0, 0, 0, 0}
Output: 2Input: arr[] = {1, 1, 1, 1, 1, 1, 1}
Output: 7Input: arr[] = {0, 0, 0, 0, 0, 0, 0}
Output: 0
Naive approach:
A simple solution is to linearly traverse the array until we find the 1’s in the array and keep count of 1s. If the array element becomes 0 then return the count of 1’s.
Time Complexity: O(N).
Auxiliary Space: O(1)
Count 1’s in a sorted binary array using Binary search recursively:
We can use Binary Search to find count in O(Logn) time. The idea is to look for the last occurrence of 1 using Binary Search. Once we find the index’s last occurrence, we return index + 1 as count.
Follow the steps below to implement the above idea:
- Do while low <= high:
- Calculate mid using low + (high – low) / 2.
- Check if the element at mid index is the last 1
- If the element is not last 1, move the low to right side recursively and return the result received from it.
- Otherwise, move the low to left recursively and return the result received from it.
The following is the implementation of the above idea.
// 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;
}
// 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 */
# 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__
// 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
// 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;
console.log("Count of 1's in given array is " +
countOnes(arr, 0, n-1));
<?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.
?>
Output
Count of 1's in given array is 4
Time complexity: O(Log(N))
Auxiliary Space: O(log(N))
Count 1’s in a sorted binary array using binary search iteratively:
Follow the steps below for the implementation:
- Do while low <= high
- Calculate the middle index say mid
- Check if arr[mid] is less than 1 then move the high to left side (i.e, high = mid – 1)
- If the element is not last 1 then move the low to the right side (i.e, low = mid + 1)
- Check if the element at the middle index is last 1 then return mid + 1
- Otherwise move to low to right (i.e, low = mid + 1)
Below is the implementation of the above approach:
#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;
}
/*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.
'''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
/*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
/* 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;
console.log( "Count of 1's in given array is "+ countOnes(arr, n));
// This code is contributed by unknown2108
Output
Count of 1's in given array is 4
Time complexity: O(Log(N))
Auxiliary Space: O(log(N))
Count 1’s in a sorted binary array using inbuilt functions:
Below is the implementation using inbuilt functions:
#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 one
auto ptr
= upper_bound(arr, arr + size, 1, greater<int>());
cout << "Count of 1's in given array is "
<< (ptr - arr);
return 0;
}
import java.util.Arrays;
public class Main {
public static void main(String[] args)
{
int[] arr = { 1, 1, 1, 1, 0, 0, 0, 0, 0 };
int size = arr.length;
// Counting the number of 1's in the array
long total = Arrays.stream(arr)
.filter(i -> i == 1)
.count();
System.out.println("Count of 1's in given array is "
+ total);
}
}
// This code is contributed by prajwal kandekar
# code
arr = [1, 1, 1, 1, 0, 0, 0, 0, 0 ]
print("Count of 1's in given array is ",arr.count(1))
# This code is contributed by Pranay Arora
using System;
using System.Linq;
class GFG{
static public void Main()
{
var total = 0;
int[] colors = { 1, 1, 1, 1, 0, 0, 0, 0, 0 };
// Count function to count the specifically
// 1 from the array
total = colors.Count(c => c == 1);
Console.WriteLine("Count of 1's in given array is "+total);
}
}
// This code is contributed by Prince Kumar
const arr = [1, 1, 1, 1, 0, 0, 0, 0, 0];
const size = arr.length;
// Pointer to the first occurrence of one
const ptr = arr.findIndex((el) => el === 0);
//If Array doesnot have 0's then findIndex will return -1
//In that case the number of 1's will be equal to size of array not -1
if(ptr === -1)
console.log(`Count of 1 's in given array is ${arr.length}`);
else
console.log(`Count of 1 's in given array is ${ptr}`);
// This code is contributed by Prajwal Kandekar
Output
Count of 1's in given array is 4
Time Complexity: O(n)
Auxiliary Space: O(1)
Contact Us