इस समस्या में, हमें एक पूर्णांक मान N दिया जाता है। हमारा कार्य अगले पुर्जों की संख्या खोजने के लिए एक प्रोग्राम बनाना है।
विरल संख्या एक विशेष प्रकार की संख्या है जिसके बाइनरी रूपांतरण में कोई सन्निकट 1 नहीं है।
Example: 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
कुशल तरीका
समस्या के लिए एक कुशल दृष्टिकोण संख्या के बिट्स में हेरफेर करना है। इसके लिए हम संख्या का बाइनरी ढूंढेंगे और उन बिट्स में हेरफेर करेंगे जहां आसन्नता होती है। कम से कम महत्वपूर्ण बिट से सबसे महत्वपूर्ण बिट की ओर बढ़ते हुए, जब हम 1 की एक जोड़ी का सामना करते हैं, तो हम दोनों 1 को 0 से बदल देंगे और अगला बिट 1 बना देंगे। और ऐसा तब तक करें जब तक हम MSB तक नहीं पहुंच जाते। और फिर संख्या बाइनरी नंबर को वापस दशमलव संख्या में बदलें जो हमारा परिणाम है।
आइए यहां एक उदाहरण लेते हैं,
एन =52
संख्या का बाइनरी 110100
. हैहम एलएसबी से आगे बढ़ेंगे और बाइनरी में लगातार 1 की पहली जोड़ी पाएंगे। यह 11 . है 0100 हाइलाइट किया गया हिस्सा। फिर, हम दोनों 1 को 0 से बदल देंगे और एक को अगले बिट में जोड़ देंगे। इससे संख्या 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