Count 1's in a sorted binary array

Last Updated : 22 Aug, 2025

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: 2
Explanation: Count of the 1's in the given array is 2.
Input: arr[] = [1, 1, 1, 1, 1, 1, 1]
Output: 7
Input: arr[] = [0, 0, 0, 0, 0, 0, 0]
Output: 0

Table of Content

[Naive approach] Using linear Search - O(n) Time and O(1) Space

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.

C++

#include <bits/stdc++.h> using namespace std; int countOnes(const vector<int> &arr) {  int count = 0;  for (int num : arr) {  if (num == 1) count++;  else break;  }  return count; } int main() {  vector<int> arr = {1, 1, 1, 1, 0, 0, 0};  cout << countOnes(arr);  return 0; }

Java

import java.util.*; class GfG {  static int countOnes(List<Integer> arr) {  int count = 0;  for (int num : arr) {  if (num == 1) count++;  else break;  }  return count;  }  public static void main(String[] args) {  List<Integer> arr = Arrays.asList(1, 1, 1, 1, 0, 0, 0);  System.out.println(countOnes(arr));  } }

Python

def countOnes(arr): count = 0 for num in arr: if num == 1: count += 1 else: break return count arr = [1, 1, 1, 1, 0, 0, 0] print(countOnes(arr))

using System; using System.Collections.Generic; class GfG {  static int CountOnes(List<int> arr)  {  int count = 0;  foreach (int num in arr)  {  if (num == 1) count++;  else break;  }  return count;  }  static void Main()  {  List<int> arr = new List<int> { 1, 1, 1, 1, 0, 0, 0 };  Console.WriteLine(CountOnes(arr));  } }

JavaScript

function countOnes(arr) {  let count = 0;  for (let num of arr) {  if (num === 1) count++;  else break;  }  return count; } const arr = [1, 1, 1, 1, 0, 0, 0]; console.log(countOnes(arr));

Output

[Expected Approach] Using Binary Search - O(log n) Time and O(1) Space

We can optimize the count of leading 1s using Binary Search in O(log n) time. The approach is:
Find the mid using low and high to find the last occurrence of 1.
If mid element is 0, move to the left half.
Else If mid contains 1 and the next element is 0 (or it's the last element), return mid + 1 as the count.
Else search the right half.

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(vector<int> &arr) {   int n = arr.size();  int ans = 0;  int low = 0, high = n - 1;    // get the middle index  while (low <= high) {   int mid = (low + high) / 2;  // If mid element is 0  if (arr[mid] == 0)  high = mid - 1;    // If element is last 1  else if (mid == n - 1 || arr[mid + 1] != 1)  return mid + 1;    // If element is not last 1   else  low = mid + 1;  }  return 0; } int main() {  vector<int> arr = { 1, 1, 1, 1, 0, 0, 0 };  cout << countOnes(arr);  return 0; }

Java

import java.util.Arrays; public class Main {  /* Returns counts of 1's in arr[low..high].   The array is assumed to be sorted in   non-increasing order */  public static int countOnes(int[] arr) {  int n = arr.length;  int ans = 0;  int low = 0, high = n - 1;    // get the middle index  while (low <= high) {   int mid = (low + high) / 2;  // If mid element is 0  if (arr[mid] == 0)  high = mid - 1;    // If element is last 1  else if (mid == n - 1 || arr[mid + 1] != 1)  return mid + 1;    // If element is not last 1   else  low = mid + 1;  }  return 0;  }  public static void main(String[] args) {  int[] arr = { 1, 1, 1, 1, 0, 0, 0 };  System.out.println(countOnes(arr));  } }

Python

# Returns counts of 1's in arr[low..high].  # The array is assumed to be sorted in  # non-increasing order def count_ones(arr): n = len(arr) low, high = 0, n - 1 # get the middle index while low <= high: mid = (low + high) // 2 # If mid element is 0 if arr[mid] == 0: high = mid - 1 # If element is last 1 elif mid == n - 1 or arr[mid + 1] != 1: return mid + 1 # If element is not last 1  else: low = mid + 1 return 0 arr = [1, 1, 1, 1, 0, 0, 0] print(count_ones(arr))

using System; using System.Linq; public class MainClass {  /* Returns counts of 1's in arr[low..high].   The array is assumed to be sorted in   non-increasing order */  public static int CountOnes(int[] arr) {  int n = arr.Length;  int ans = 0;  int low = 0, high = n - 1;    // get the middle index  while (low <= high) {   int mid = (low + high) / 2;  // If mid element is 0  if (arr[mid] == 0)  high = mid - 1;    // If element is last 1  else if (mid == n - 1 || arr[mid + 1] != 1)  return mid + 1;    // If element is not last 1   else  low = mid + 1;  }  return 0;  }  public static void Main(string[] args) {  int[] arr = { 1, 1, 1, 1, 0, 0, 0 };  Console.WriteLine(CountOnes(arr));  } }

JavaScript

// Returns counts of 1's in arr[low..high].  // The array is assumed to be sorted in  // non-increasing order function countOnes(arr) {  const n = arr.length;  let low = 0, high = n - 1;    // get the middle index  while (low <= high) {  const mid = Math.floor((low + high) / 2);  // If mid element is 0  if (arr[mid] === 0)  high = mid - 1;    // If element is last 1  else if (mid === n - 1 || arr[mid + 1] !== 1)  return mid + 1;    // If element is not last 1   else  low = mid + 1;  }  return 0; } const arr = [1, 1, 1, 1, 0, 0, 0]; console.log(countOnes(arr));

Output

[Alternate Approach] Using inbuilt functions

In C++, Java, and C#, we can use inbuilt functions that take only O(log n) time. However, in Python, we can apply binary search using inbuilt functions on non-decreasing elements, but it will take O(n) time, not O(log n). JavaScript does not provide a built-in binary search function.

C++

#include <bits/stdc++.h> using namespace std; int main() {  vector<int> arr = {1, 1, 1, 1, 0, 0, 0, 0, 0};  int size = arr.size();  // Iterayot to the first occurrence of one  auto ptr = lower_bound(arr.begin(), arr.end(), 0, greater<int>());  cout << (ptr - arr.begin());  return 0; }

Java

import java.util.Arrays; public class GfG {  public static void main(String[] args) {  int[] arr = {1, 1, 1, 1, 0, 0, 0, 0, 0};  // Find the first occurrence of 0 using binary search  int index = Arrays.binarySearch(arr, 0);  // If 0 is found, count of 1s is its index; else, all are 1s  int countOnes = (index >= 0) ? index : -(index + 1);  System.out.println(countOnes);  } }

Python

# code arr = [1, 1, 1, 1, 0, 0, 0, 0, 0 ] print(arr.count(1)) # This code is contributed by Pranay Arora

using System; class GfG {  static int CountOnes(int[] arr)  {  // Find the first occurrence of 0 using Binary Search  int index = Array.FindIndex(arr, x => x == 0);    // If no 0 is found, all elements are 1s  return index == -1 ? arr.Length : index;  }  static void Main()  {  int[] arr = { 1, 1, 1, 1, 0, 0, 0, 0, 0 };  Console.WriteLine(CountOnes(arr));  } }

JavaScript

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 (ptr === -1)  console.log(arr.length); else  console.log(ptr);