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):
if high >= low:
mid = low + (high - low) / 2
# Check if we find the 0, 1 transition
if ((mid == high or arr[mid+1] == 0) and (arr[mid] == 1)):
return mid+1 # If not found search in right side if middle element is 1
if arr[mid] == 1:
return count_1s_bs(arr, (mid+1), high) # else search in left side
return count_1s_bs(arr, low, mid-1) return 0
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.
