# C Program Count 1’s in a sorted binary array

C Program Count 1’s in a sorted binary array – Searching and Sorting – 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.

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 C implementation of above idea.

C Program

[pastacode lang=”c” manual=”%2F%2F%20C%2B%2B%20program%20to%20count%20one’s%20in%20a%20boolean%20array%0A%23include%20%3Ciostream%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F*%20Returns%20counts%20of%201’s%20in%20arr%5Blow..high%5D.%20%20The%20array%20is%0A%20%20%20assumed%20to%20be%20sorted%20in%20non-increasing%20order%20*%2F%0Aint%20countOnes(bool%20arr%5B%5D%2C%20int%20low%2C%20int%20high)%0A%7B%0A%20%20if%20(high%20%3E%3D%20low)%0A%20%20%7B%0A%20%20%20%20%2F%2F%20get%20the%20middle%20index%0A%20%20%20%20int%20mid%20%3D%20low%20%2B%20(high%20-%20low)%2F2%3B%0A%20%0A%20%20%20%20%2F%2F%20check%20if%20the%20element%20at%20middle%20index%20is%20last%201%0A%20%20%20%20if%20(%20(mid%20%3D%3D%20high%20%7C%7C%20arr%5Bmid%2B1%5D%20%3D%3D%200)%20%26%26%20(arr%5Bmid%5D%20%3D%3D%201))%0A%20%20%20%20%20%20return%20mid%2B1%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20element%20is%20not%20last%201%2C%20recur%20for%20right%20side%0A%20%20%20%20if%20(arr%5Bmid%5D%20%3D%3D%201)%0A%20%20%20%20%20%20return%20countOnes(arr%2C%20(mid%20%2B%201)%2C%20high)%3B%0A%20%0A%20%20%20%20%2F%2F%20else%20recur%20for%20left%20side%0A%20%20%20%20return%20countOnes(arr%2C%20low%2C%20(mid%20-1))%3B%0A%20%20%7D%0A%20%20return%200%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20functions%20*%2F%0Aint%20main()%0A%7B%0A%20%20%20bool%20arr%5B%5D%20%3D%20%7B1%2C%201%2C%201%2C%201%2C%200%2C%200%2C%200%7D%3B%0A%20%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%20%20cout%20%3C%3C%20%22Count%20of%201’s%20in%20given%20array%20is%20%22%20%3C%3C%20countOnes(arr%2C%200%2C%20n-1)%3B%0A%20%20%20return%200%3B%0A%7D” message=”c” highlight=”” provider=”manual”/]

Output:

`Count of 1's in given array is 4`

Time complexity of the above solution is O(Logn)

## Web browser project in c, c program to open a website/url

Web browser project in c, c program to open a website/url – c programming – It will launch Firefox web browser to open a website so it should be installed.

## Tips to Get Your Car Repaired After An Accident

Car accidents are an event that happens all over the country with regularity. It seems like the wheels of fate was unfavorable to you … and your car was involved…

## Top 10 Grey Hat Hackers 2018

Grey hat hackers that do hacking bit the ethical and non-ethical. These are the persons who knows extraordinary hacking traps

## C++ Programming – Program to add two polynomials

C++ Programming – Program to add two polynomials – Mathematical Algorithms – Addition is simpler than multiplication of polynomials. We initialize result

## C Programming – Subset Sum Problem

C Programming – Subset Sum Problem – Dynamic Programming Given a set of non-negative integers, and a value sum, determine if there is a subset

## JAVA Program Count 1’s in a sorted binary array

JAVA Program Count 1’s in a sorted binary array – Searching and Sorting – 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.