# Count Ones (1s) in a Sorted Binary Array

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: 0``````

Naive 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 make `low = mid +1`
• if `mid == 0` or `arr[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)