समस्या विवरण
हमारे पास एक अनुक्रम जनरेटर है जो 1 से शुरू होता है। प्रत्येक चरण में 0→10 और 1→01 हो जाता है।
- चरण 1: 01
- चरण 2: 1001
- चरण 3: 01101001
- चरण 4: 1001011001101001
लक्ष्य दिए गए चरण संख्या के लिए लगातार '00' जोड़ों की संख्या ज्ञात करना है।
पैटर्न विश्लेषण
- चरण 1: 0 जोड़े
- चरण 2: 1 जोड़ा
- चरण 3: 1 जोड़ा
- चरण 4: 3 जोड़े
- चरण 5: 5 जोड़े
- चरण 10: 171 जोड़े
अनुक्रम 2 की घात में बढ़ता है और 12 लंबाई के बाद दोहराता है। प्रत्येक 12-लंबाई पैटर्न में 2 जोड़े होते हैं।
सूत्र: tmp = 2^steps / 12, pairs = 1 + 2*tmp
एल्गोरिदम
- चरण संख्या
decimalलें - यदि
decimal <= 1→ 0 लौटाएँ - यदि
decimal == 2 या 3→ 1 लौटाएँ - अन्यथा:
temp = pow(2, decimal) / 12,count = 2*temp + 1 countलौटाएँ
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
int Zero_pairs(int decimal) {
if (decimal <= 1) return 0;
if (decimal == 2 || decimal == 3) return 1;
long long temp = (1LL << decimal) / 12; // 2^decimal / 12
return 2 * temp + 1;
}
int main() {
int decimal = 7;
cout << "Count: " << Zero_pairs(decimal);
return 0;
}
आउटपुट
Count: 21
