Count 1’s in a sorted binary array

October 18, 2024

Count 1’s in a sorted binary array

In the Count 1’s in a sorted binary array Problem, we have to find a number of 1 in a sorted array of only zeros and ones. The problem can be solved using binary search. In this article, we will provide a C++ solution with an explanation

Count 1’s in a sorted binary array Problem Description

Count 1’s in a sorted binary array Problem Description

Given a binary array of n elements. Output the count of 1 in the array.

Input

  • First-Line contains a single integer n – the size of the array.
  • Next-line contains n binary integers – the elements of the array.

Output

  • The required count.

Count 1’s in a sorted binary array Problem Solution

Brute Force

The idea here is to use a single loop and traverse all elements of the array. While traversing the array if we encounter a 1, we increment the count.

Time Complexity – O(n)

Space Complexity – O(1)

Code

Run 
#include <bits/stdc++.h>
using namespace std;
int count(int arr[], int n)
{
    int ct = 0;
    for (int i = 0; i < n; i++)
        if (arr[i] == 1)
            ct++;
    return ct;
}
int main()
{
    int n;
    cin >> n;
    int arr[n];

    for (int i = 0; i < n; i++)
        cin >> arr[i];

    cout << count(arr, n) << endl;
    return 0;
}

Output

6
0 0 0 0 1 1
2

Optimized approach

In the optimized approach, since we know the array consists of only 0s and 1s in sorted order, we find first occurrence of 1.

Then count of one will be equal t0 n – index of first occurrence of 1.

We can easily find the first occurence of 1 by binary search or using C++ STL upperbound.

Time Complexity – O(nlogn)

Space Complexity – O(1)

Code

Run 
#include <bits/stdc++.h>
using namespace std;
/*
    We can also use C++ STL instead of custom binary search

    ans = n – upperbound(arr,arr+n,0)
*/
int count(int arr[], int n)
{
    int st = 0, ed = n - 1, ans = n;

    while (st <= ed)
    {
        int mid = (st + ed) / 2;
        if (arr[mid] == 1)
        {
            ans = mid;
            ed = mid - 1;
        }
        else
        {
            st = mid + 1;
        }
    }

    return n - ans;
}
int main()
{
    int n;
    cin >> n;
    int arr[n];

    for (int i = 0; i < n; i++)
        cin >> arr[i];

    cout << count(arr, n) << endl;
    return 0;
}

Output

6
0 0 0 0 1 1
2

2 comments on “Count 1’s in a sorted binary array”