Count Ones (1s) in a Sorted Binary Array
Srivastava Bodakunti
0
40
Problem: Given a sorted binary array, we need to count 1s in this array.
Examples:
Input: arr[] = {0, 0, 0, 1, 1, 1, 1}
Output: 4
Input: arr[] = {1, 1, 1, 1, 1}
Output: 5
Input: arr[] = {0, 0, 0, 0}
Output: 0Naive solution is to simply traverse through array and as array is sorted and contains only 0s and 1s, once we encounter 1 we know its remaining elements are also 1s. So get the index of 1st occurring 1 and subtract the index from total number of elements. This has a time complexity of O(n) in worst case.
Another efficient solution is to make use of Binary Search ( as in case of Index of First Occurrence):
- we find the mid index, if
arr[mid] == 0, we know 1s are in right half, so makelow = mid +1 - if
mid == 0orarr[mid -1] == 0, we subtract the mid from total number of elements and return it - else we know that the 1s are in left half as well, so we make
high = mid - 1
Solution:
/**
* <p><b>Count Ones:</b> is to count ones in a sorted binary array</p>
* <p><b>Time Complexity:</b> O(log n)</p>
* <p><b>Usage:</b></p>
* {@code
* int[] binaryArr = {0, 0, 1, 1, 1, 1, 1};
* CountOnes.in(binaryArr);
* }
*/
public class CountOnes {
/**
* <b>FLow:</b>
* <p>Make use of two Binary Search (as in case of Index of First Occurrence)
* <ul>
* <li>we find the mid index, if arr[mid] == 0, we know 1s are in right half,
* so make low = mid +1</li>
* <li>if mid == 0 or arr[mid -1] == 0, we subtract the mid from total number
* of elements and return it</li>
* <li>else we know that the 1s are in left half as well, so we make
* high = mid - 1</li>
* </ul>
* @param arr integer array
* @return count of ones (1s)
*/
public static int in(int[] arr) {
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == 0) {
low = mid + 1;
} else {
if (mid == 0 || arr[mid - 1] == 0) {
return arr.length - mid;
} else {
high = mid - 1;
}
}
}
return 0;
}
}
Time Complexity: O(log n), Auxiliary Space: O(1)
