# Count 1’s in a sorted binary array

Given a binary array 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

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

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

A simple solution is to linearly traverse the array. The time complexity of the simple solution is O(n). We can use Binary Search to find count in O(Logn) time. The idea is to look for last occurrence of 1 using Binary Search. Once we find the index last occurrence, we return index + 1 as count.

The following is the implementation of above idea.

## C++

 `// C++ program to count one's in a boolean array ` `#include ` `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 program to test above functions */` `int` `main() ` `{ ` `   ``bool` `arr[] = {1, 1, 1, 1, 0, 0, 0}; ` `   ``int` `n = ``sizeof``(arr)/``sizeof``(arr); ` `   ``cout << ``"Count of 1's in given array is "` `<< countOnes(arr, 0, n-1); ` `   ``return` `0; ` `}`

## Python

 `# 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 function ` `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 program to test above functions */` `    ``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 */`

/div>

## 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 program to test above functions */` `    ``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

 `= ``\$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 program to test above functions */` `\$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 of the above solution is O(Logn)