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:

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

Implementation in python for the same

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:

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.