हमें एक पूर्णांक संख्या दी गई है मान लीजिए, N जिसे भाजक माना जाता है और इसे 1 - N से शुरू होने वाली संख्याओं से विभाजित किया जाएगा और कार्य उन भाजकों की संख्या की गणना करना है जिनमें दी गई संख्या N से विभाजित होने पर भागफल से अधिक सेट बिट्स हों।
उदाहरण के लिए
इनपुट - int N = 6
आउटपुट - N को विभाजित करने पर भागफल से अधिक सेट बिट्स वाले भाजकों की संख्या: 5
व्याख्या - सबसे पहले, हम संख्या N को 1 - N से शुरू होने वाली संख्याओं से विभाजित करेंगे और भाजक और भागफल के सेट बिट्स की गणना करेंगे यानी
1-> N = 6 /1(1) = 6(2) = 1 < 2 = विचार नहीं किया गया
2-> N = 6 /2(1) = 3(2) = 2 = 2 = विचार किया गया
3-> N = 6 /3(2) = 2(1) = 2 > 1 = विचार किया गया
4-> N = 6 /4(1) = 1(1) = 1 = 1 = विचार किया गया
5-> N = 6 /5(2) = 1(1) = 2 > 1 = विचार किया गया
6-> N = 6 /6(2) = 1(1) = 2 >1 = विचार किया गया
जैसा कि हम देख सकते हैं, हम विचार किए गए मामले लेंगे और आउटपुट 5 होगा।
इनपुट - int N = 10
आउटपुट - N को विभाजित करने पर भागफल से अधिक सेट बिट्स वाले भाजकों की संख्या: 8
व्याख्या - सबसे पहले, हम संख्या N को 1 - N से शुरू होने वाली संख्याओं से विभाजित करेंगे और भाजक और भागफल के सेट बिट्स की गणना करेंगे यानी
1-> N = 10 /1(1) = 10(2) = 1 < 2 = विचार नहीं किया गया
2-> N = 10 /2(1) = 5(2) = 2 = 2 = विचार किया गया
3-> N = 10 /3(2) = 3(2) = 2 = 2 = विचार किया गया
4-> N = 10 /4(1) = 2(1) = 1 < 2 = विचार नहीं किया गया
5-> N = 10 /5(2) = 2(1) = 2 > 2 = विचार किया गया
6-> N = 10 /6(2) = 1(1) = 2 >1 = विचार किया गया
7-> N = 10 /7(3) = 1(1) = 3 >1 = विचार किया गया
8-> N = 10 /8(1) = 1(1) = 1 = 1 = विचार किया गया
9-> N = 10 /9(2) = 1(1) = 2 > 2 = विचार किया गया
10-> N = 10 /10(2) = 1(1) = 2 > 1 = विचार किया गया
जैसा कि हम देख सकते हैं, हम विचार किए गए मामले लेंगे और आउटपुट 8 होगा।
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण
- एक धनात्मक पूर्णांक संख्या N इनपुट करें और इसे फ़ंक्शन divisors_quotient() में तर्क के रूप में पास करें।
- फ़ंक्शन divisors_quotient() के अंदर
- N - फ़ंक्शन set_quo(N) को कॉल + 1 लौटाएं और फ़ंक्शन set_quo() पर जाएं
- फ़ंक्शन set_quo() के अंदर
- एक अस्थायी वेरिएबल start और end बनाएं और start को 1 और end को sqrt(N) से इनिशियलाइज़ करें।
- start < end तक WHILE लूप शुरू करें और एक अस्थायी वेरिएबल temp बनाएं और इसे (start + end) / 2 सेट करें
- चेक करें IF(verify() फ़ंक्शन को कॉल करें और temp और N को तर्क के रूप में पास करें) तो end को temp सेट करें
- अन्यथा, start को temp + 1 सेट करें
- IF(!verify() फ़ंक्शन को कॉल करें और temp और N को तर्क के रूप में पास करें) तो start + 1 लौटाएं।
- अन्यथा, start लौटाएं
- फ़ंक्शन verify() के अंदर
- चेक करें IF(फ़ंक्शन val_bit(temp/val) कॉल फ़ंक्शन val_bit(val) से कम है) तो true लौटाएं अन्यथा false लौटाएं
- फ़ंक्शन val_bit() के अंदर
- परिणाम संग्रहीत करने के लिए एक अस्थायी वेरिएबल count घोषित करें।
- val के मान होने तक WHILE लूप शुरू करें। लूप के अंदर, val को val / 2 सेट करें और count को 1 से बढ़ाएं।
- count लौटाएं।
उदाहरण
#include <bits/stdc++.h> using namespace std; int val_bit(int val) { int count = 0; while (val) { val = val / 2; count++; } return count; } bool verify(int val, int temp) { if (val_bit(temp / val) <= val_bit(val)) { return true; } return false; } int set_quo(int N) { int start = 1; int end = sqrt(N); while (start < end) { int temp = (start + end) / 2; if (verify(temp, N)) { end = temp; } else { start = temp + 1; } } if (!verify(start, N)) { return start + 1; } else { return start; } } int divisors_quotient(int N) { return N - set_quo(N) + 1; } int main() { int N = 10; cout << "Count of divisors having more set bits than quotient on dividing N are: " << divisors_quotient(N); return 0; } यदि हम उपरोक्त कोड चलाते हैं तो यह निम्नलिखित आउटपुट उत्पन्न करेगा -
आउटपुट
Count of divisors having more set bits than quotient on dividing N are: 8
