इस समस्या में, हमें केवल 0 और 1 से मिलकर एक बाइनरी सरणी बिन [] दिया जाता है। हमारा काम है शून्य की संख्या ज्ञात करना ।
सरणी को क्रमबद्ध किया जाता है यानी सभी 0 को 1 के बाद एक साथ व्यवस्थित किया जाता है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr[] = {1, 1, 1, 0, 0, 0, 0} आउटपुट
4
समाधान दृष्टिकोण
समस्या का एक सरल समाधान इस तथ्य का उपयोग कर रहा है कि सरणी को क्रमबद्ध किया गया है, अर्थात सरणी में 0 की संख्या को सरणी में 0 की पहली घटना का उपयोग करके पाया जा सकता है। पहली घटना के बाद सभी मान शून्य होंगे।
सरणी में 0 की पहली घटना को खोजने के लिए। हम खोज एल्गोरिदम का उपयोग कर सकते हैं।
रैखिक खोज - पहले 0 के लिए रैखिक खोज में, हम पूरे सरणी को तब तक पार करेंगे जब तक कि पहले 0 का सामना नहीं किया जाता है, फिर हम पहली घटना और सरणी के आकार का उपयोग करके गिनती वापस कर देंगे। इस समाधान का उपयोग करके हम समस्या की समय जटिलता को 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<<"The count of zeros in array is "<<countZerosArr(arr, n);
return 0;
} आउटपुट
The count of zeros in array is 5
बाइनरी सर्च - बाइनरी सर्च में, हम एरे के सेक्शन को इस आधार पर विभाजित करके पहला 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<<"The count of zeros in array is "<<countZerosArr(arr, n);
return 0;
} आउटपुट
The count of zeros in array is 7