C++ का उपयोग करके शून्यों की संख्या खोजना

समस्या विवरण

इस समस्या में, हमें केवल 0 और 1 से युक्त एक बाइनरी सरणी bin[] दी गई है। हमारा कार्य शून्यों की संख्या खोजना है।

सरणी क्रमबद्ध है यानी सभी 0, 1 के बाद एक साथ व्यवस्थित हैं।

उदाहरण

इनपुट

arr[] = {1, 1, 1, 0, 0, 0, 0}

आउटपुट

4

हल का दृष्टिकोण

समस्या का एक सरल समाधान इस तथ्य का उपयोग करना है कि सरणी क्रमबद्ध है, यानी सरणी में 0 की संख्या सरणी में 0 की पहली घटना का उपयोग करके खोजी जा सकती है। पहली घटना के बाद सभी मान शून्य होंगे।

सरणी में 0 की पहली घटना खोजने के लिए। हम खोज एल्गोरिदम का उपयोग कर सकते हैं।

विधि 1: रैखिक खोज (O(N))

#include <iostream> 
using namespace std; 

int findFirstZero(int arr[], int n) {
    for(int i = 0; i < n; i++) {
        if(arr[i] == 0)
            return i;
    }
    return -1;
}

int countZerosArr(int arr[], int n) {
    int firstOccZero = findFirstZero(arr, n);
    if (firstOccZero == -1)
        return 0;
    return (n - firstOccZero);
}

int main() {
    int arr[] = {1, 1, 1, 1, 0, 0, 0, 0, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "सरणी में शून्यों की संख्या है " << countZerosArr(arr, n);
    return 0;
}

विधि 2: बाइनरी खोज (O(log N)) - इष्टतम

बाइनरी खोज में, हम सरणी के खंड को इस आधार पर विभाजित करके पहली 0 खोजेंगे कि मध्य पर तत्व 1 है या 0। और 0 की पहली घटना का इंडेक्स वापस करें।

#include <iostream> 
using namespace std; 

int findFirstZero(int arr[], int start, int end) {
    if (end >= start) {
        int mid = start + (end - start) / 2;
        if ((mid == 0 || arr[mid - 1] == 1) && arr[mid] == 0)
            return mid;
        if (arr[mid] == 1)
            return findFirstZero(arr, (mid + 1), end);
        else
            return findFirstZero(arr, start, (mid - 1));
    }
    return -1;
}

int countZerosArr(int arr[], int n) {
    int firstOccZero = findFirstZero(arr, 0, n - 1);
    if (firstOccZero == -1)
        return 0;
    return (n - firstOccZero);
}

int main() {
    int arr[] = {1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "सरणी में शून्यों की संख्या है " << countZerosArr(arr, n);
    return 0;
}

आउटपुट

सरणी में शून्यों की संख्या है 7

जटिलता विश्लेषण

मुख्य शर्त

सरणी में सभी 1 पहले होने चाहिए, उसके बाद सभी 0 (गैर-बढ़ते क्रम)।