हमें एक संख्या दी गई है और कार्य है 0 से दी गई संख्या तक की रेंज में उन संख्याओं की गिनती करना जिनमें ठीक एक सेट बिट (set bit) है।
बाइनरी संख्या में सेट बिट को 1 से दर्शाया जाता है। जब भी हम किसी पूर्णांक का बाइनरी प्रतिनिधित्व निकालते हैं तो यह 0 और 1 के संयोजन से बनता है। अंक 1 को कंप्यूटर के संदर्भ में सेट बिट कहा जाता है।
इनपुट - int num = 15
आउटपुट - रेंज [0, 15] में केवल 1 सेट बिट वाली संख्याओं की गिनती: 4
व्याख्या - 1 (0001), 2 (0010), 4 (0100), 8 (1000) - इन चार संख्याओं में ठीक एक सेट बिट है।
उपयोग किया गया दृष्टिकोण (नाइव)
- संख्या इनपुट करें और फंक्शन में पास करें।
countवेरिएबल लें।- लूप i = 1 से number तक।
__builtin_popcount(i)से सेट बिट्स गिनें।- यदि 1 है तो काउंट बढ़ाएं।
कुशल दृष्टिकोण
केवल 2 की घातें (1, 2, 4, 8, 16, ...) में ठीक एक सेट बिट होती है। इसलिए हम केवल 2 से गुणा करते हुए गिनती कर सकते हैं।
temp = 1से शुरू करें।- जब तक
temp <= number:count++,temp *= 2।
उदाहरण (नाइव दृष्टिकोण)
#include <iostream>
using namespace std;
int set_bits(int number) {
int count = 0;
for (int i = 1; i <= number; i++) {
int temp = __builtin_popcount(i);
if (temp == 1) count++;
}
return count;
}
int main() {
int number = 15;
cout << "Count of numbers having only 1 set bit in the range [0, " << number << "] are: " << set_bits(number);
return 0;
} आउटपुट
Count of numbers having only 1 set bit in the range [0, 15] are: 4
उदाहरण (कुशल दृष्टिकोण)
#include <iostream>
using namespace std;
int set_bits(int number) {
int count = 0;
int temp = 1;
while (temp <= number) {
count++;
temp = temp * 2;
}
return count;
}
int main() {
int number = 15;
cout << "Count of numbers having only 1 set bit in the range [0, " << number << "] are: " << set_bits(number);
return 0;
} आउटपुट
Count of numbers having only 1 set bit in the range [0, 15] are: 4
