समस्या कथन
एक संख्या n को देखते हुए, कार्य दिए गए n के द्विआधारी प्रतिनिधित्व में दो तत्काल 1 के बीच अधिकतम 0 का पता लगाना है। वापसी -1 यदि बाइनरी प्रतिनिधित्व में दो 1 से कम हो
उदाहरण
यदि इनपुट संख्या 35 है तो इसका द्विआधारी प्रतिनिधित्व है -
00100011
उपरोक्त द्विआधारी प्रतिनिधित्व में दो तत्काल 1 के बीच 3 0 हैं। अतः उत्तर 3 है।
एल्गोरिदम
हम इस समस्या को हल करने के लिए बिटवाइज़ शिफ्ट ऑपरेटर का उपयोग कर सकते हैं। हमें n के द्विआधारी प्रतिनिधित्व में दो तत्काल 1 की स्थिति खोजने और इन स्थिति के अंतर को अधिकतम करने की आवश्यकता है।
- यदि संख्या 0 है या 2 की शक्ति है तो -1 लौटें
- सबसे पहले दायें सबसे अधिक 1 की स्थिति के साथ चर prev को प्रारंभ करें। यह पहले देखे गए 1 की स्थिति को संग्रहीत करता है।
- एक और वेरिएबल कर्व लें जो पिछले 1 के ठीक बाद तत्काल 1 की स्थिति को संग्रहीत करता है।
- कर् - पिछला - 1 का अंतर लें, यह तत्काल 1 के बीच 0 की संख्या होगी और इसकी तुलना 0 के पिछले अधिकतम मान से करें और पिछला अपडेट करें यानी; prev=cur अगले पुनरावृत्ति के लिए।
- IU वेरिएबल सेटबिट का उपयोग करें, जो n के सभी बिट्स को स्कैन करता है और यह पता लगाने में मदद करता है कि क्या वर्तमान बिट्स 0 या 1 है। सहायक चर सेटबिट का उपयोग करें, जो n के सभी बिट्स को स्कैन करता है और यह पता लगाने में मदद करता है कि वर्तमान बिट्स 0 या 1 है या नहीं।
उदाहरण
आइए अब एक उदाहरण देखें -
#include <bits/stdc++.h>
using namespace std;
int getMaxZeros(int n) {
if (n == 0 || (n & (n - 1) == 0)) {
return -1;
}
int setBit = 1;
int prev = 0;
int i;
for (i = 1; i < sizeof(int) * 8; ++i) {
++prev;
if ((n & setBit) == setBit) {
setBit = setBit << 1;
break;
}
setBit = setBit << 1;
}
int maxZeros = INT_MIN;
int cur = prev;
for (int j = i + 1; j <= sizeof(int) * 8; ++j) {
++cur;
if ((n & setBit) == setBit) {
if (maxZeros < (cur - prev - 1)) {
maxZeros = cur - prev - 1; prev = cur;
}
}
setBit = setBit << 1;
}
return maxZeros;
}
int main() {
int n = 35;
cout << "Maximum zeros = " << getMaxZeros(n) << endl;
return 0;
} आउटपुट
Maximum zeros = 3