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.

Traverse through array
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.

Special thanks to Sai bargav Nellepalli for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article