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

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

स्ट्रिंग S जादुई है क्योंकि '1' और '2' वर्णों की सन्निहित घटनाओं की संख्या को संयोजित करने से स्ट्रिंग S ही उत्पन्न होती है।
स्ट्रिंग S के पहले कुछ घटक निम्नलिखित हैं - S ="1221121221221121122……"
यदि हम क्रमागत '1' और '2' को S में समूहित करते हैं, तो यह होगा - 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" है। इसमें तीन 1s हैं, इसलिए 3 लौटाएं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

यदि n <=0 है, तो 0 लौटाएं, यदि n <=3, तो 1 लौटाएं
ret :=1, आकार n की एक सरणी arr बनाएं
गिरफ्तारी[0] :=1, गिरफ्तारी[1] :=2, गिरफ्तारी[2] :=2
सिर:=2, पूंछ:=3 और अंक:=1
जबकि पूंछ
मैं के लिए 0 से एआर तक की सीमा में [सिर] - 1
- arr[tail] :=num
- यदि संख्या 1 है और पूंछ
- पूंछ को 1 से बढ़ाएं
- अगर पूंछ>=n, तो लूप तोड़ें
संख्या =अंक XOR 3
सिर 1 से बढ़ाएं

रिटर्न रिटर्न

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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;
   }
};
main(){
   Solution ob;
   cout << (ob.magicalString(6));
}