हमें इनपुट के रूप में एक नंबर n दिया गया है। लक्ष्य x मानों को इस प्रकार ज्ञात करना है कि शर्त (n xor x)=(nx) धारण करती है। साथ ही x रेंज [0,n] में है।
आइए उदाहरणों के साथ समझते हैं
इनपुट - n=10
आउटपुट - x <=n के मानों की गणना जिसके लिए (n XOR x) =(n - x) हैं - 4
स्पष्टीकरण − 10 xor x =10-x − 0, 2, 8 और 10 के साथ x का मान।
इनपुट - n=15
आउटपुट - x <=n के मानों की गणना जिसके लिए (n XOR x) =(n - x) हैं - 16
स्पष्टीकरण − 15 xor x =15-x − 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 और 15 के साथ x का मान।
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
हम दो दृष्टिकोणों का उपयोग करेंगे। लूप के लिए उपयोग करने वाला पहला बेवकूफ दृष्टिकोण। जितना संभव हो सके x के लिए i=0 से i<=n तक ट्रैवर्स करना शुरू करें। अब जांचें कि क्या (n - i ==(n ^ i) //xor)। अगर सही वेतन वृद्धि गिनती है।
-
पूर्णांक चर n को इनपुट के रूप में लें।
-
फ़ंक्शन unique_pair(int arr[], int size) सरणी और इसकी लंबाई लेता है और अद्वितीय जोड़े की संख्या देता है जैसे कि जोड़ी में (arr[i],arr[j]) अनुक्रमणिका i
-
गिनती का प्रारंभिक मान 0 के रूप में लें।
-
पूर्णांक युग्मों वाला एक समुच्चय 'se' लीजिए। (सेट<जोड़ी
-
लूप के लिए दो का उपयोग करके ट्रैवर्सिंग एआर [] शुरू करें। i=0 से i
-
प्रत्येक जोड़ी के लिए हमेशा i
-
लूप के लिए दोनों के अंत में, count=se.size() अपडेट करें।
-
काउंट में अब 'से' में कई जोड़े हैं। (सभी अद्वितीय हैं)।
-
परिणाम के रूप में वापसी की गिनती।
कुशल दृष्टिकोण
इस दृष्टिकोण में हम पहले n को इसके बाइनरी समकक्ष में परिवर्तित करेंगे। हम जानते हैं कि
1 xor 0 =1-0
1 xor 1 =1-1
लेकिन
0 xor 0 0-1
0 xor 1 ≠ 0-1
तो n के द्विआधारी प्रतिनिधित्व में प्रत्येक 1 के लिए, 2 मामले हैं। n के द्विआधारी प्रतिनिधित्व में p वाले के लिए, 2p मान होंगे जो शर्त को पूरा करते हैं।
सूचकांक मैं। फिर कुल अद्वितीय जोड़ियों के लिए ऐसी अलग-अलग संख्याएं जोड़ें।
-
पूर्णांक चर n को इनपुट के रूप में लें।
-
फ़ंक्शन unique_pair(int arr[], int size) सरणी और इसकी लंबाई लेता है और अद्वितीय जोड़े की संख्या देता है जैसे कि जोड़ी में (arr[i],arr[j]) अनुक्रमणिका i
-
गिनती का प्रारंभिक मान 0 के रूप में लें।
-
number=bitset<8>(n).to_string();
. का उपयोग करके n को स्ट्रिंग में बदलें -
लंबाई लें =संख्या। लंबाई ()।
-
अनुक्रमणिका i=0 से i<लंबाई तक लूप के लिए उपयोग करते हुए ट्रैवर्स स्ट्रिंग। प्रत्येक 1 वेतन वृद्धि गणना के लिए।
-
गिनती=पाउ(2,गिनती) को x के अंतिम मान के रूप में सेट करें।
-
परिणाम के रूप में वापसी की गिनती।
उदाहरण (बेवकूफ दृष्टिकोण)
#include<bits/stdc++.h>
using namespace std;
int count_values(int n){
int count = 0;
for (int i = 0; i <= n; i++){
if (n - i == (n ^ i)){
count++;
}
}
return count;
}
int main(){
int n = 25;
cout<<"Count of values of x <= n for which (n XOR x) = (n – x) are: "<<count_values(n);
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
Count of values of x <= n for which (n XOR x) = (n – x) are: 8
उदाहरण (कुशल दृष्टिकोण)
#include<bits/stdc++.h>
using namespace std;
int count_values(int n){
int count = 0;
string number = bitset<8>(n).to_string();
int length = number.length();
for (int i = 0; i < length; i++){
if (number.at(i) == '1')
{ count++; }
}
count = (int)pow(2, count);
return count;
}
int main(){
int n = 25;
cout<<"Count of values of x <= n for which (n XOR x) = (n – x) are: "<<count_values(n);
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
Count of values of x <= n for which (n XOR x) = (n – x) are: 8