# Count 1’s in Sorted binary Array

Problem Statement: Given a sorted binary array (consisting of only 0’s and 1’s), the task is to find the total number of 1’s in the given array.

Examples:

```Example 1:
Input: [0,0,0,1,1]
Output: 2
Explanation:  Total number of 1’s in given array is 2, so answer will be 2

Example 2:
Input: [0,0,0,0,0,0,1]
Output: 1
Explanation:  Total number of 1’s in given array is 1

Example 3:
Input: [0,0,0,0,0,0,0]
Output: 0
Explanation:  There are no 1’s in the given array So, output will be 0
```

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

### Solution 1:

Brute force:

A brute force approach is to traverse through the array, and while traversing if 1 is encountered for the first time in the array that means all the elements to the right-hand side of this first occurrence of 1 will be 1’s only, as the array is sorted.

1. Traverse through array
2. Find the index where you are getting the first occurrence of 1 then return the answer as Length of the array – index of the first occurrence of 1

Code:

## C++ Code

``````#include<bits/stdc++.h>
using namespace std;

int totalOnes(int arr[],int n) {
int ans = 0;
//traversing through array
for (int i = 0; i < n; i++) {
//found 1 in array for the first time
if (arr[i] == 1) {
ans = n - i;
break; // exit from loop as we found answer
}
}

return ans;

}
int main()
{
int binaryArray[] = {0,0,0,1,1,1};
cout<<"Total number of 1's: "<<totalOnes(binaryArray,6);
}
``````

Output: Total number of 1’s: 3

Time complexity: O(n)

Space complexity: O(1)

## Java Code

``````public class TUF {
public static void main(String[] args) {
int[] binaryArray = {0,0,0,1,1,1};
System.out.println("Total number of 1's: " + totalOnes(binaryArray));
}

private static int totalOnes(int[] arr) {
int n = arr.length;
int ans = 0;
//traversing through array
for (int i = 0; i < arr.length; i++) {
//found 1 in array for the first time
if (arr[i] == 1) {
ans = n - i;
break; // exit from loop as we found answer
}
}

return ans;

}
}
``````

Output: Total number of 1’s: 3

Time complexity: O(n)

Space complexity: O(1)

### Solution 2: Optimized approach

Intuition & Approach:

Find the first occurrence index of 1 and all the elements on the right side of this index will be 1 only.

Since the array is sorted we can find the first occurrence of 1 using the Binary Search algorithm

• If the element at the middle index is 0 then make start index = middle index +1
• Else if the element at middle index is 1 then update answer as the middle index ( because the middle index element may be the first occurrence of 1) and make the end index = middle index – 1
• Return ans

Code:

## C++ Code

``````#include<bits/stdc++.h>
using namespace std;

int totalOnes(int arr[],int n) {
int start = 0, end = n - 1;
int ans = 0;

while (start <= end) {
int mid = start + (end - start) / 2;
if (arr[mid] == 0) {
start = mid + 1;
}

else if (arr[mid] == 1) {
ans = n - mid;

end = mid - 1;
}
}
return ans;

}
int main()
{
int binaryArray[] = {0,0,0,1,1,1};
cout<<"Total number of 1's: "<<totalOnes(binaryArray,6);
}
``````

Output: Total number of 1’s: 3

Time complexity: O(logn) because the binary search algorithm is used

Space complexity: O(1) as extra space is not used.

## Java Code

``````public class TUF {
public static void main(String[] args) {
int[] binaryArray = {0,0,0,1,1,1};
System.out.println("Total number of 1's: " + totalOnes(binaryArray));
}

private static int totalOnes(int[] arr) {
int start = 0, end = arr.length - 1;
int ans = 0, n = arr.length;

while (start <= end) {
int mid = start + (end - start) / 2;

if (arr[mid] == 0) {
start = mid + 1;
}

else if (arr[mid] == 1) {
ans = n - mid;

end = mid - 1;
}
}
return ans;
}
}
``````

Output: Total number of 1’s: 3

Time complexity: O(logn) because the binary search algorithm is used

Space complexity: O(1) as extra space is not used.