हमें बाइनरी अनुक्रम के लिए कई बिट्स n इनपुट के रूप में दिए गए हैं। लक्ष्य यहां 2n लंबाई का बाइनरी अनुक्रम ढूंढना है जैसे कि इसके पहले और दूसरे आधे बिट्स का योग समान हो। पहले n बिट्स और अगले n बिट्स का योग समान है।
हमारे पास एक बाइनरी अनुक्रम है इसलिए किसी भी स्थान पर रखे जाने वाले अंकों का एकमात्र विकल्प 0 और 1 है। पहले और दूसरे आधे के लिए n बिट्स पर, संभावित संयोजनों की संख्या है:
सभी शून्यों के साथ n बिट्स (0 1's) nC0= 1
1 1's के साथ n बिट्स nC1
2 1's के साथ n बिट्स nC2
.
.
n 1's के साथ n बिट्स nCn
2n बिट्स के लिए
- पहले आधे में 0 1's और दूसरे आधे में 0 1's nC0 X nC0
- पहले आधे में 1 1's और दूसरे आधे में 1 1's nC1 X nC1
- पहले आधे में 2 1's और दूसरे आधे में 2 1's nC2 X nC2
- ..............
- पहले आधे में n 1's और दूसरे आधे में n 1's nCn X nCn
ऐसे कुल संयोजन= nC0*nC0 + nC1*nC1+.......+nCn*nCn
=(nC0)²+(nC1)²+...........+(nCn)²
इनपुट
n=1
आउटपुट
पहले और दूसरे आधे बिट्स का योग समान होने वाले अनुक्रम: 2
व्याख्या: संभावित 2*1=2 बिट अनुक्रम 00,01,10,11 इन चार में से 01 और 10 का योग=1
इनपुट
n=2
आउटपुट
पहले और दूसरे आधे बिट्स का योग समान होने वाले अनुक्रम: 6
व्याख्या: संभावित 2*2 = 4-बिट अनुक्रम 0000,0001,0010,0011,0100,0101,0110,0111,1000,1001,1010,1011,1100,1101,1110,1111
इनमें से पहले 2 और अंतिम 2 बिट्स का योग समान होने वाले अनुक्रम:
0000,0101,0110,1001,1010,1111, कुल=6
प्रयुक्त दृष्टिकोण
- पूर्णांक 'bits' संख्या संग्रहीत करता है।
- फ़ंक्शन findSeq(int n) n को इनपुट के रूप में लेता है और उपरोक्त पहले और दूसरे आधे 2n बिट्स का योग समान होने वाले अनुक्रमों की संख्या लौटाता है।
- चर nCi का उपयोग प्रारंभिक मान =1 संग्रहीत करने के लिए किया जाता है क्योंकि nC0 1 है।
- ans=0 आरंभ करें, जो nCi*nCi के योग के रूप में ऐसे अनुक्रमों की गणना करेगा।
- i=0 से n तक शुरू करके ans में nCi*nCi जोड़ें, उपरोक्त सूत्र के अनुसार प्रत्येक nCi की गणना करें।
- for लूप के अंत में 'ans' में मौजूद परिणाम को गणना के रूप में लौटाएं।
उदाहरण कोड
#include<iostream> using namespace std; // सम लंबाई वाले अनुक्रमों की संख्या लौटाता है int findSeq(int n){ int nCi=1; //nC0=1 int ans = 1; for (int i = 1; i<=n ; i++){ //nCi=(nCi-1)*(nCi/nCi-1) // nCi/nC(i-1) = (n+1-i)/i; nCi = (nCi * (n+1-i))/i; ans += nCi*nCi; } return ans; } int main(){ int bits = 2; cout << "पहले और दूसरे आधे बिट्स का योग समान होने वाले बाइनरी अनुक्रमों की संख्या: "<<findSeq(bits); return 0; } आउटपुट
पहले और दूसरे आधे बिट्स का योग समान होने वाले बाइनरी अनुक्रमों की संख्या: 6