Count Ones - C++ Solution

1. Introduction

In this post, we will explore an efficient approach to a common problem in binary arrays - counting the number of 1's in a sorted binary array. The array consists only of 0's and 1's, and since it is sorted, all 1's are positioned after the 0's.

Problem

The challenge is to efficiently count the total number of 1's in a sorted binary array. A straightforward approach might involve iterating over the entire array, but we aim for a more efficient solution.

2. Solution Steps

1. Use binary search to find the index of the first occurrence of 1.

2. If 1 is not found, return 0.

3. The number of 1's is the difference between the array's size and the index of the first 1.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to find the index of the first occurrence of 1
int findFirstOne(const vector<int>& nums) {
    int low = 0, high = nums.size() - 1, res = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] == 1) {
            res = mid;
            high = mid - 1; // Search in the left half
        } else {
            low = mid + 1;
        }
    }
    return res;
}

// Function to count the number of 1's
int countOnes(const vector<int>& nums) {
    int firstOneIndex = findFirstOne(nums);
    if (firstOneIndex == -1) return 0; // No 1's in the array
    return nums.size() - firstOneIndex;
}

int main() {
    vector<int> nums = {0, 0, 0, 0, 1, 1, 1};
    cout << "Count of 1's: " << countOnes(nums) << endl;
    return 0;
}

Output:

Count of 1's: 3

Explanation:

The function countOnes calculates the total number of 1's in a sorted binary array. It first finds the index of the first occurrence of 1 using a binary search. The number of 1's is then determined by the difference between the size of the array and this index. For example, in the array [0, 0, 0, 0, 1, 1, 1], the first 1 occurs at index 4, giving us 3 as the count of 1's.