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, তবে আউটপুট হবে ৩, কারণ ম্যাজিক্যাল স্ট্রিং-এ প্রথম ৬ উপাদান হল “12211”। এতে তিনটি 1 আছে, তাই ৩ ফেরত দিন।

এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব −

যদি n <= 0, তবে ০ ফেরত দিন, যদি n <= 3, তবে ১ ফেরত দিন
ret := 1, n আকারের একটি arr অ্যারে তৈরি করুন
arr[0] := 1, arr[1] := 2, arr[2] := 2
head := 2, tail := 3 এবং num := 1
যখন tail < n
- i = 0 থেকে arr[head] – ১ পর্যন্ত
  - arr[tail] := num
  - যদি num 1 হয় এবং tail < n, তবে ret ১ বৃদ্ধি করুন
  - tail ১ বৃদ্ধি করুন
  - যদি tail >= n, তবে লুপ ভাঙুন
- num = num XOR 3
- head ১ বৃদ্ধি করুন
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;    } }; main(){    Solution ob;    cout << (ob.magicalString(6)); }