समस्या कथन
एक संख्या n दी गई है, कार्य दिए गए n के बाइनरी प्रतिनिधित्व में दो तत्काल 1 के बीच अधिकतम 0 की संख्या ढूंढना है। यदि बाइनरी प्रतिनिधित्व में दो से कम 1 हैं तो -1 वापस करें।
उदाहरण
यदि इनपुट संख्या 35 है तो इसका बाइनरी प्रतिनिधित्व है:
00100011
उपरोक्त बाइनरी प्रतिनिधित्व में दो तत्काल 1 के बीच 3 शून्य हैं। इसलिए उत्तर 3 है।
एल्गोरिदम
हम इस समस्या को हल करने के लिए बिटवाइज शिफ्ट ऑपरेटर का उपयोग कर सकते हैं। हमें n के बाइनरी प्रतिनिधित्व में दो तत्काल 1 की स्थिति ढूंढनी होगी और इन स्थितियों के अंतर को अधिकतम करना होगा।
- यदि संख्या 0 या 2 की घात है तो -1 वापस करें।
- पहले दाएं सबसे 1 की स्थिति के साथ वेरिएबल prev को प्रारंभ करें। यह पहले देखे गए 1 की स्थिति संग्रहीत करता है।
- एक और वेरिएबल cur लें जो prev के ठीक बाद तत्काल 1 की स्थिति संग्रहीत करता है।
- cur - prev - 1 का अंतर लें, यह दो तत्काल 1 के बीच 0 की संख्या होगी और इसकी तुलना 0 के पिछले अधिकतम मान से करें और prev को अपडेट करें यानी अगले पुनरावृति के लिए prev = cur।
- वेरिएबल setBit का उपयोग करें, जो 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
