C++ में जादुई स्ट्रिंग

मान लीजिए एक स्ट्रिंग है। उस स्ट्रिंग को एक जादुई स्ट्रिंग S कहा जाता है, जिसमें केवल '1' और '2' होते हैं और निम्नलिखित नियमों का पालन करती है:

स्ट्रिंग S जादुई है क्योंकि वर्णों '1' और '2' की सन्निकट घटनाओं की संख्या को जोड़ने से स्ट्रिंग S स्वयं उत्पन्न होती है।
स्ट्रिंग S के पहले कुछ घटक निम्नलिखित हैं: S = "1221121221221121122......"
यदि हम S में लगातार '1' और '2' को समूहित करते हैं, तो यह होगा: 1 22 11 2 1 22 1 22 11 2 11 22 ...... और प्रत्येक समूह में '1' या '2' की घटनाएं हैं: 1 2 2 1 1 2 1 2 2 1 2 2 ......

अब मान लीजिए हमारे पास इनपुट के रूप में एक पूर्णांक N है, जादुई स्ट्रिंग S में पहले N नंबर में '1' की संख्या ढूंढें। इसलिए यदि इनपुट 6 है, तो आउटपुट 3 होगा, क्योंकि जादुई स्ट्रिंग में पहले 6 तत्व "12211" हैं। इसमें तीन 1 हैं, इसलिए 3 लौटाएं।

हल का दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

यदि n <= 0, तो 0 लौटाएं, यदि n <= 3, तो 1 लौटाएं
ret := 1, आकार n की एक सरणी arr बनाएं
arr[0] := 1, arr[1] := 2, arr[2] := 2
head := 2, tail := 3, num := 1
while tail < n:
- i = 0 से arr[head] - 1 तक:
  - arr[tail] := num
  - यदि num == 1 और tail < n, तो ret को 1 से बढ़ाएं
  - tail को 1 से बढ़ाएं
  - यदि tail >= n, तो लूप तोड़ें
- num = num XOR 3
- head को 1 से बढ़ाएं
ret लौटाएं

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 

class Solution { 
public: 
    int magicalString(int n) { 
        if(n <= 0) return 0; 
        if(n <= 3) return 1; 
        int ret = 1; 
        vector<int> arr(n); 
        arr[0] = 1; 
        arr[1] = 2; 
        arr[2] = 2; 
        int head = 2; 
        int tail = 3; 
        int num = 1; 
        while(tail < n){ 
            for(int i = 0; i < arr[head]; i++){ 
                arr[tail] = num; 
                if(num == 1 && tail < n) ret++; 
                tail++; 
                if(tail >= n) break; 
            } 
            num ^= 3; 
            head++; 
        } 
        return ret; 
    } 
}; 

int main(){ 
    Solution ob; 
    cout << (ob.magicalString(6)); 
}