इस समस्या में, हमें n तत्वों से युक्त एक सरणी गिरफ्तारी दी जाती है जो या तो 0 या 1 हैं। हमारा कार्य पड़ोसियों को भरने के न्यूनतम पुनरावृत्तियों का उपयोग करके 1 के साथ सरणी भरना है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट: गिरफ्तारी [] ={0, 1, 1, 0, 0, 1}
आउटपुट: 1
समाधान दृष्टिकोण -
समस्या को हल करने के लिए, हमें इस तथ्य को जानना होगा कि यदि 1 किसी स्थिति में मौजूद है तो यह दो पड़ोसी 0 को 1 में बदल सकता है।
अगर, गिरफ्तारी [i] 1 है।
फिर, arr[i-1] और arr[i+1] को 1 में बदल दिया जाएगा।
इसका उपयोग करके, इनमें से किसी एक मामले का उपयोग करके समाधान पाया जा सकता है -
मामला 1: ब्लॉक में ब्लॉक के प्रारंभ और अंत में 1 होता है। शेष सभी मान 0 हैं। शून्य की संख्या गिनें।
पुनरावृत्तियों की संख्या =ज़ीरोकाउंट / 2 अगर गिनती सम है
पुनरावृत्ति की संख्या =(शून्य गणना -1)/2 यदि गणना विषम है
मामला 2: ब्लॉक में ब्लॉक के प्रारंभ या अंत में सिंगल 1 होता है और बाकी सभी मान 0 होते हैं।
पुनरावृत्तियों की संख्या =शून्य गणना
केस 3: ब्लॉक में कोई 1 नहीं है। प्रिंट -1 यह दर्शाता है कि 1 को भरना संभव नहीं है।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#include<iostream>
using namespace std;
int countIterationFill1(int arr[], int n) {
bool oneFound = false;
int iterationCount = 0;
for (int i=0; i<n; ) {
if (arr[i] == 1)
oneFound = true;
while (i<n && arr[i]==1)
i++;
int zeroCount = 0;
while (i<n && arr[i]==0) {
zeroCount++;
i++;
}
if (oneFound == false && i == n)
return -1;
int itrCount;
if (i < n && oneFound == true) {
if (zeroCount & 1 == 0)
itrCount = zeroCount/2;
else
itrCount = (zeroCount+1)/2;
zeroCount = 0;
}
else{
itrCount = zeroCount;
zeroCount = 0;
}
iterationCount = max(iterationCount, itrCount);
}
return iterationCount;
}
int main() {
int arr[] = {0, 1, 1, 0, 0, 1, 0, 0, 0, 1};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The number of iterations to fill 1's is "<<countIterationFill1(arr, n);
return 0;
} आउटपुट -
The number of iterations to fill 1's is 2