Given a sorted binary array, efficiently find the number of 1’s in it.

For example,

**Input: **A[] = [0, 0, 0, 0, 1, 1, 1]

** Output: **Total number of 1’s present are 3

**Input: **A[] = [0, 0, 1, 1, 1, 1, 1]

** Output: **Total number of 1’s present are 5

A simple solution would be to run a linear search on the array and find the first occurrence of one. Then the output will be number of elements in the array minus index of the first occurrence of one. The problem with this approach is that its worst case time complexity is O(n).

We can easily solve this problem in O(log(n)) time by using Recursion. The idea is to take advantage of the fact that the input is sorted (i.e. all 0’s followed by all 1’s). We split the array to two halves and recurse for both the halves. If the last element of the sub-array is 0, then all 0’s are present in it since it is sorted and we return 0 from the function. If the first element of the array is 1, then all its elements are 1’s only since array is sorted and we return number of elements in that partition.

## C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <stdio.h> // Function to find number of 1's in a sorted binary array int count(int arr[], int n) { // if last element of the array is 0, no ones can // be present in it since it is sorted if (arr[n - 1] == 0) { return 0; } // if first element of the array is 1, all its elements // are ones only since it is sorted if (arr[0]) { return n; } // divide array into left and right sub-array and recurse return count(arr, n/2) + count(arr + n/2, n - n/2); } // main function int main(void) { int arr[] = { 0, 0, 0, 0, 1, 1, 1 }; int n = sizeof(arr) / sizeof(arr[0]); printf("Total number of 1's present are %d", count(arr, n)); return 0; } |

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
#include <iostream> #include <algorithm> // main function int main() { int arr[] = { 0, 0, 0, 0, 1, 1, 1 }; int count = std::upper_bound(std::begin(arr), std::end(arr), 1) - std::lower_bound(std::begin(arr), std::end(arr), 1); std::cout << "Total number of 1's present are " << count; return 0; } |

## Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
class Util { // Function to find number of 1's in a sorted binary array public static int count(int A[], int left, int right) { // if last element of the array is 0, no ones can // be present in it since it is sorted if (A[right] == 0) { return 0; } // if first element of the array is 1, all its elements // are ones only since it is sorted if (A[left] == 1) { return (right - left + 1); } // divide array into left and right sub-array and recurse int mid = (left + right) / 2; return count(A, left, mid) + count(A, mid + 1, right); } public static void main(String[] args) { int[] A = { 0, 0, 0, 1 }; System.out.println("Total number of 1's present are " + count(A, 0, A.length - 1)); } } |

`Output:`

Total number of 1’s present are 3

The time complexity of above solution is O(log(n)) and auxiliary space used by the program is O(log(n)) for recursive function.

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

This can be done using

upper_bound(a.begin(), a.end(), 1) - lower_bound(a.begin(), a.end(), 1)HEADER FILE:

Thanks. We have added this solution to the post. Since an array is used, the code should be:

or

Happy coding 🙂

There is the problem in your site. It remove my half code during comment post.

Could you please use ideone.com and share the link with us 🙂

You are using “First Occurence Algorithm” which is fine too.

The java code gets StackOverflow with {0,0,0,1} input. One way to solve this is by changing the last two lines as below

Thanks a lot for bringing this to our notice. We have updated the code. Happy coding 🙂