Count the number of 1’s in an array sorted in decreasing order.

Question:

You are given an array that is sorted in decreasing order and has only 0’s and 1’s. You need to find the number of 1’s present in it.

Example:

array = {1,1,1,1,1,0,0,0}
Output = 5

array = {1,1,1,1}
Output = 4

array = {0,0,0,0,0}
Output = 0

Solution:

We can solve it by binary search.

We need to find the last occurrence of 1 and return index+1 as the result.

We need to take care of some of the cases:

1. To check if the mid index is the last element, First check if the element at mid index is 1
if (arr[mid] == 1)

2. check if the element next to mid index is 0
if(arr[mid+1] == 0)

3. Or mid index is equal to the end index
if(arr[mid+1] == end)

The above 3 if statement can be combined into one statement as below:
if ( (mid == end || arr[mid+1] == 0) && (arr[mid] == 1))

4. If mid index is not the last index of 1, then either move to left half or right half.

5. If (arr[mid] == 1) it means that, there are more 1’s towards it right. Hence move towards right.

6. else it means that, the mid index is 0, so 1’s might be present at left part of the array.

Solution in C++

#include <iostream>
using namespace std;


int count_number_of_1_s( int arr[], int len)
{
    int start = 0;
    int end = len - 1;

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

        if ((mid == end || arr[mid+1] == 0) && (arr[mid] == 1))  
        { 
            return mid+1; 
        } 
        
        if (arr[mid] == 1)
        {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }

    return -1;
}

int main(void) 
{ 
    int arr[] = {1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0}; 
    int len = sizeof(arr) / sizeof(arr[0]); 
    int result = count_number_of_1_s(arr, len);

    cout<<"The number of 1's are "<<result<<endl;

    return 0; 
} 

Output:

The number of 1’s are 8