C++-এ পাসিং কার জোড়া সংখ্যা গণনা

আমাদের একটি অ্যারে দেওয়া আছে যেটিতে শুধু 0 এবং 1 আছে। 1 মানে পশ্চিম দিকের দিকে যাওয়া গাড়ি, 0 মানে পূর্ব দিকের দিকে যাওয়া গাড়ি। পাসিং কার জোড়া হল এমন (A,B) যাতে 0 <= A < B < N, arr[A]=0 (পূর্ব) এবং arr[B]=1 (পশ্চিম)।

উদাহরণ

ইনপুট: arr[] = {1,0,1,0,1}

আউটপুট: ৩

ব্যাখ্যা: জোড়া: (arr[1],arr[2]), (arr[1],arr[4]), (arr[3],arr[4])।

ইনপুট: arr[] = {1,0,0,0,0}

আউটপুট: ০

অ্যালগরিদম (দক্ষ পদ্ধতি - শেষ থেকে ট্রাভার্সাল)

1. অ্যারে এবং আকার ইনপুট নিন।
2. শেষ থেকে শুরু করুন। temp = স الساحلেই ১-এর সংখ্যা।
3. যদি arr[i]==1 হয়, temp++।
4. যদি arr[i]==0 হয়, count += temp (কারণ এই ০-এর সাথে সব ১ জোড়া বানাবে)।
5. সময় জটিলতা: O(n), স্পেস: O(1)।

C++ বাস্তবায়ন (দক্ষ)

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

int count_cars(int arr[], int size) {
    int count = 0;
    int temp = 0;
    while (size >= 1) {
        if (arr[size - 1] == 1) temp++;
        else count += temp;
        size--;
    }
    return count;
}

int main() {
    int arr[] = {1, 1, 0, 1, 1};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of passing car pairs are: " << count_cars(arr, size);
    return 0;
}

আউটপুট

Count of passing car pairs are: 2