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.
Total
1
Shares

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)

 

Leave a Reply

Your email address will not be published. Required fields are marked *

You May Also Like