दिए गए समस्या में हमें एक संख्या का मान खोजने की आवश्यकता है जिसके दिए गए रेंज L, R के बीच सभी सेट बिट्स हों। उदाहरण के लिए:
इनपुट: L = 1, R = 5 आउटपुट: 62 व्याख्या: दिए गए L और R का बाइनरी रूप में प्रस्तुतिकरण 0..0111110 है इनपुट: L = 1, R = 4 आउटपुट: 30 व्याख्या: दिए गए L और R का बाइनरी रूप में प्रस्तुतिकरण 0..11110 है
समाधान का दृष्टिकोण
दिए गए समस्या में, हम दो दृष्टिकोणों पर चर्चा करने जा रहे हैं, ब्रूट फोर्स और कुशल दृष्टिकोण।
ब्रूट फोर्स
इस दृष्टिकोण में, हम केवल दिए गए रेंज के माध्यम से ट्रैवर्स करने जा रहे हैं और दिए गए रेंज में 2 की सभी घातों को जोड़ेंगे, और वह हमारा उत्तर होगा।
उदाहरण
#include<bits/stdc++.h>
using namespace std;
int main() {
int L = 1, R = 3; // दी गई रेंज
int ans = 0; // हमारा उत्तर
for(int i = L; i <= R; i++) // पूरी रेंज के माध्यम से ट्रैवर्स करना
ans += pow(2, i); // उत्तर में मान जोड़ना।
cout << ans << "\n";
}
आउटपुट
14
इस दृष्टिकोण में, हम केवल रेंज के माध्यम से ट्रैवर्स कर रहे हैं और रेंज में संख्याओं की 2 की घात को बस जोड़ रहे हैं। इस प्रोग्राम की समय जटिलता O(N) है, जहां N हमारी रेंज का आकार है। लेकिन हम दिए गए प्रश्न में बिट्स के ज्ञान को लागू करके समय जटिलता को और सुधार सकते हैं।
कुशल दृष्टिकोण
इस दृष्टिकोण में, हम केवल एक सूत्र बनाएंगे जो हमारे लिए उत्तर की गणना करेगा।
उदाहरण
#include<bits/stdc++.h>
using namespace std;
int main() {
int L = 1, R = 3; // दी गई रेंज
int ans = 0; // हमारा उत्तर
// सूत्र: (1 << (R+1)) - (1 << L)
ans = ((1 << (R + 1)) - 1) ^ ((1 << L) - 1);
cout << ans << "\n";
}
आउटपुट
14
इस दृष्टिकोण में, हम उत्तर की गणना के लिए एक सूत्र बनाते हैं।
उपरोक्त कोड की व्याख्या
जैसा कि आप जानते हैं, हमें दी गई रेंज में सेट बिट्स वाली संख्या की गणना करने की आवश्यकता है, इसलिए इस दृष्टिकोण में, हम एक संख्या ढूंढते हैं जिसके 0 से R तक सभी बिट्स सेट हों। फिर हमें एक ऐसी संख्या घटानी होगी जिसके 1 से (L-1) तक सभी बिट्स सेट हों, और इस प्रकार हम इस अवलोकन को सूत्रबद्ध करते हैं। दिए गए कोड की समग्र समय जटिलता O(1) है जो स्थिर समय जटिलता है जिसका अर्थ है कि हम किसी भी उत्तर की गणना स्थिर समय में कर सकते हैं।
निष्कर्ष
यह लेख "L-वें और R-वें इंडेक्स के बीच केवल सेट बिट्स वाली संख्या" के लिए एक प्रोग्राम बनाएगा। हमने इस समस्या के लिए C++ प्रोग्राम और इसे हल करने के पूर्ण दृष्टिकोण (सामान्य और कुशल) को भी सीखा। हम इसी प्रोग्राम को C, Java, Python और अन्य भाषाओं में लिख सकते हैं। आशा है कि आपको यह लेख मददगार लगा होगा।
