# Interview Question: Count 1’s in a sorted binary array

# Problem statement:

A binary array sorted in decreasing order is given. We need to count the number of 1’s in it.

**Examples:**

Input: arr[] = {1, 1, 0, 0, 0, 0, 0}

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

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

Output: 0

**Solution**: A simple solution is to do a linear traversal of the array.

**Implementation **in python for the same

def count_1s(arr):

count = 0

for i in range(len(arr)):

if arr[i] == 0:

break

count += 1

return count

arr=[1, 1, 1, 1, 0, 0, 0]

print(count_1s(arr))

**Analysis**: The time complexity of this solution is O(n) as we have a for loop to process every element in the array.

**Better Solution**: The above solution works. Can we do any better? Is there any property of the given data we can leverage?

**Idea: **We know the given array is sorted. If we can do a binary search logic and somewhat find the transition of 1’s and 0’s we are good. That implementation will be in O(log n).

**Implementation:**

def count_1s_bs(arr, low, high):

ifhigh >=low:

mid=low+(high-low)/2

# Check if we find the 0, 1 transition

if((mid==highorarr[mid+1]==0)and(arr[mid]==1)):

returnmid+1 # If not found search in right side if middle element is 1

ifarr[mid]==1:

returncount_1s_bs(arr, (mid+1), high) # else search in left side

returncount_1s_bs(arr, low, mid-1)return0

arr=[1, 1, 1, 1, 0, 0, 0]

print(count_1s_bs(arr))

# Conclusion:

The above solution run in O(log n). A similar approach can be applied to a variety of similar problems like

- Given array count no.of 0’s, 1's and 2’s=> given array has only 0’s, 1’s and 2’s and sorted.
- Given array of 0’s and 1’s sort. Can you sort it with O(n) ?

I leave it here. There can be a lot of other variations. All you need to do is understand the problem clearly and to apply your data structures algorithms knowledge to arrive at right solution. For some of the problems, choosing a right data structure to represent given data itself will solve problem. We will cover examples in these categories in future posts.