इस समस्या में, हमें एक पूर्णांक मान N दिया जाता है। हमारा कार्य अगली विरल संख्या ढूंढने के लिए एक प्रोग्राम बनाना है।
विरल संख्या एक विशेष प्रकार की संख्या है जिसके बाइनरी रूपांतरण में कोई आसन्न 1 नहीं होते।
उदाहरण: 5(101) , 16(10000)
समस्या विवरण – दी गई संख्या N के लिए, हमें N से बड़ी सबसे छोटी संख्या ढूंढनी है जो विरल संख्या है।
आइए एक उदाहरण से समस्या को समझते हैं,
इनपुट
N = 7
आउटपुट
8
व्याख्या
8 का बाइनरी 1000 है जो इसे N से बड़ी सबसे छोटी विरल संख्या बनाता है।
समाधान दृष्टिकोण
इस समस्या का एक सरल समाधान N से बड़ी सभी संख्याओं की जांच करना है। और तब तक रुकना जब तक हमें पहली विरल संख्या न मिल जाए।
इसके लिए हमें N से अनंत तक लूप करना होगा और प्रत्येक संख्या के लिए जांचना होगा कि यह विरल संख्या है या नहीं। यदि हां, तो लूप तोड़ें अन्यथा जारी रखें।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला प्रोग्राम,
उदाहरण
#include<iostream> using namespace std; bool isSpareNumber(int N){ int currentBit = (N&1); int nextBit ; while (N!= 0){ nextBit = currentBit; currentBit = (N&1); N >>= 1; if(nextBit == currentBit && nextBit == 1 && currentBit == 1) return false ; } return true; } int findNextSparseNumber(int N) { while(1){ if(isSpareNumber(N)) return N; N++; } return -1; } int main() { int N = 564; cout<<"The number is "<<N<<endl; cout<<"The next Sparse Number is "<<findNextSparseNumber(N); return 0; }आउटपुट
The number is 564 The next Sparse Number is 576
कुशल दृष्टिकोण
समस्या का एक कुशल दृष्टिकोण संख्या के बिट्स में हेरफेर करना है। इसके लिए हम संख्या का बाइनरी ढूंढेंगे और उन बिट्स में हेरफेर करेंगे जहां आसन्नता होती है। LSB से MSB तक पार करते हुए, जब हमें 1 की एक जोड़ी मिलती है, तो हम दोनों 1 को 0 से बदल देंगे और अगले बिट को 1 बना देंगे। और ऐसा तब तक करेंगे जब तक हम MSB तक न पहुंच जाएं। और फिर बाइनरी संख्या को वापस दशमलव संख्या में बदल देंगे जो हमारा परिणाम है।
आइए यहां एक उदाहरण लेते हैं,
N = 52
संख्या का बाइनरी 110100 है
हम LSB से पार करेंगे और बाइनरी में लगातार 1 की पहली जोड़ी ढूंढेंगे। यह 110100 हाइलाइट किया गया भाग है। फिर, हम दोनों 1 को 0 से बदल देंगे और अगले बिट में 1 जोड़ देंगे। इससे संख्या 1000000 बनती है, जिसका बाइनरी रूपांतरण 64 है।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला प्रोग्राम,
उदाहरण
#include<iostream> using namespace std; int findNextSparseNumber(int N) { int spNum[16]; int n = 0; while (N != 0) { spNum[n] = (N&1); n++; N >>= 1; } n++; int lastCorrectedBit = 0; for (int i= 0 ; i< n; i++) { if (spNum[i] == 1 && spNum[i-1] == 1 && spNum[i+1] != 1){ spNum[i+1] = 1; for (int j=i; j>=lastCorrectedBit; j--) spNum[j] = 0; lastCorrectedBit = i+1; } } int sparseNumber = 0; for (int i =0; i<n-1; i++) sparseNumber += spNum[i]*(1<<i); return sparseNumber; } int main() { int N = 564; cout<<"The number is "<<N<<endl; cout<<"The next Sparse Number is "<<findNextSparseNumber(N); return 0; }आउटपुट
The number is 564 The next Sparse Number is 576
