পুনরাবৃত্ত অঙ্ক সহ সংখ্যা বানানোর পদ্ধতি গণনা C++-এ

একটি স্ট্রিং হিসেবে সংখ্যা দেওয়া থাকলে (যেখানে অঙ্কগুলো রিপিট হতে পারে), সেটিকে কতভাবে বানানো/বোঝানো যায় তা গণনা করতে হবে। যেমন "11" → "double one" বা "one one"।

উদাহরণ

ইনপুট: "11211"

বর্ণনা পদ্ধতি:

1. One one two one one
2. Double one two one one
3. One one two double one
4. Double one two double one

অ্যালগরিদম

1. স্ট্রিং ট্রাভার্স করুন।
2. সังলগ্ন সমান অঙ্কের গোষ্ঠী (run) খুঁজুন।
3. দৈর্ঘ্য L-এর গোষ্ঠীর জন্য 2^(L-1) ভাব সম্ভব।
4. সব গোষ্ঠীর সম্ভাবনা গুণ করুন।

C++ কোড উদাহরণ

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

long long countSpellWays(string str) {
    long long count = 1;
    int n = str.length();
    
    for (int i = 0; i < n; i++) {
        int runLen = 1;
        while (i + 1 < n && str[i+1] == str[i]) {
            runLen++;
            i++;
        }
        count *= (1LL << (runLen - 1)); // 2^(runLen-1)
    }
    return count;
}

int main() {
    string str = "222211";
    cout << "Ways to spell: " << countSpellWays(str);
    return 0;
}

ইনপুট

"222211"

আউটপুট

16