পাইথনে অক্ষর সাজানোর উপায় সংখ্যা বের করুন যাতে প্রতিটি প্রিফিক্স ও সাফিক্সে B-র সংখ্যা A-র চেয়ে বেশি হয়

ধরুন, একটি স্ট্রিং আছে যাতে n সংখ্যক A এবং 2n সংখ্যক B আছে। আমাদের সার্বিক সাজানোর উপায় সংখ্যা বের করতে হবে যাতে প্রতিটি প্রিফিক্স (prefix) এবং প্রতিটি সাফিক্স (suffix)-এ B-র সংখ্যা A-র সংখ্যার চেয়ে বেশি বা সমান থাকে।

সুতরাং, যদি ইনপুট হয় n = 2, তবে আউটপুট হবে 4 কারণ দুটি A এবং চারটি B আছে, তাই সম্ভব সাজানোর উপায়গুলো হল [BBAABB, BABABB, BBABAB, BABBAB]।

এটি সমাধান করার জন্য, আমরা নিচের ধাপগুলো অনুসরণ করব:

• solve নামে একটি মেথড ডিফাইন করুন, যেটি n নেবে
• যদি n 1 সমান হয়, তবে:
  • 1 ফেরত দিন
• যদি n 2 সমান হয়, তবে:
  • 4 ফেরত দিন
• যদি n বিজোড় (odd) হয়, তবে:
  • solve(floor((n-1)/2))^2 ফেরত দিন
• অন্যথায়:
  • solve(floor(n/2))^2 ফেরত দিন

উদাহরণ

বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন:

def solve(n):
    if n == 1:
        return 1
    if n == 2:
        return 4
    if n % 2 != 0:
        return solve((n-1)//2)**2
    else:
        return solve(n//2)**2

n = 2
print(solve(n))

ইনপুট

2

আউটপুট

4