C++-এ সর্টেড বাইনারি অ্যারেতে ১-এর সংখ্যা গণনা (Count 1's in Sorted Binary Array)

এই টিউটোরিয়ালে, শুধু ০ এবং ১ ধারণকারী একটি সর্টেড অ্যারেতে ১-এর সংখ্যা বাইনারি সার্চ দিয়ে দ্রুত গণনা করার পদ্ধতি আলোচনা করা হয়েছে।

বাইনারি সার্চ পদ্ধতি

সর্টেড অ্যারেতে ১গুলো আগে থাকে, ০গুলো পরে। শেষ ১-এর পজিশন বাইনারি সার্চ দিয়ে খুঁজুন।

C++ প্রোগ্রাম উদাহরণ

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

int countOnes(bool arr[], int low, int high) {
    if (high >= low) {
        int mid = low + (high - low) / 2;
        if ((mid == high || arr[mid+1] == 0) && (arr[mid] == 1))
            return mid + 1;
        if (arr[mid] == 1)
            return countOnes(arr, mid + 1, high);
        return countOnes(arr, low, mid - 1);
    }
    return 0;
}

int main() {
    bool arr[] = {1, 1, 1, 1, 0, 0, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of 1's in given array is " << countOnes(arr, 0, n-1);
    return 0;
}

আউটপুট

Count of 1's in given array is 4