C++ এ ম্যাজিকাল স্ট্রিং

ধরুন একটি স্ট্রিং আছে। এই স্ট্রিংটিকে একটি জাদুকরী স্ট্রিং 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 আকারের একটি অ্যারে অ্যারে তৈরি করুন
আরর[0] :=1, arr[1] :=2, arr[2] :=2
মাথা :=2, লেজ :=3 এবং সংখ্যা :=1
যখন লেজ
আমি রেঞ্জ 0 থেকে arr[head] – 1
- arr[tail] :=সংখ্যা
- যদি num হয় 1 এবং tail
- লেজ 1 দ্বারা বাড়ান
- যদি লেজ>=n হয়, তাহলে লুপ ভেঙে দিন
num =num 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));
}