# 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 1^{st} 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)