पासिंग कार जोड़ों की गणना - C++

समस्या विवरण

हमें 0 और 1 वाली एक सरणी दी गई है। 1 = पश्चिम की ओर जाती कार, 0 = पूर्व की ओर जाती कार। पासिंग कार जोड़ा: (0,1) जहाँ 0 का इंडेक्स 1 के इंडेक्स से कम हो।

उदाहरण

इनपुट: arr[] = {1,0,1,0,1}

आउटपुट: 3

व्याख्या: जोड़े: (arr[1],arr[2]), (arr[1],arr[4]), (arr[3],arr[4])

इनपुट: arr[] = {1,0,0,0,0}

आउटपुट: 0

दृष्टिकोण

साधारण: दो नेस्टेड लूप, O(n²)।

कुशल: अंत से पार करें। temp = अब तक मिले 1 की संख्या। जब 0 मिले, count += temp। O(n) समय।

C++ कार्यान्वयन (कुशल)

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

int count_cars(int arr[], int size) {
    int count = 0, 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: " << count_cars(arr, size);
    return 0;
}

आउटपुट

Count: 2