পাইথনে n দৈর্ঘ্যের লেক্সিকোগ্রাফিক্যালি সবচেয়ে ছোট স্ট্রিং থেকে k-তমটি বের করার প্রোগ্রাম

মান লক্ষ্য করুন আমাদের কাছে একটি সংখ্যা n এবং অন্য একটি মান k আছে। এখন এমন স্ট্রিং বিবেচনা করুন যেটি শুধুমাত্র "0", "1", এবং "2" দিয়ে গঠিত এবং কোনো ক্যারেক্টার একসাথে দুবার রিপিট হয় না। আমাদের কাজ হল দৈর্ঘ্য n এর такие স্ট্রিংগুলো বানানো এবং তাদের মধ্যে k-তম লেক্সিকোগ্রাফিক্যালি সবচেয়ে ছোট স্ট্রিংটি বের করা। যদি k-তম স্ট্রিং না থাকে, তবে খালি স্ট্রিং রিটার্ন করুন।

উদাহরণস্বরূপ, যদি ইনপুট হয় n = 4, k = 2, তবে আউটপুট হবে "0120"।

সমাধানের ধাপসমূহ:

একটি solve() মেথড ডিফাইন করুন যা s, k এবং last নেবে।
যদি s == 0 হয়, তবে খালি স্ট্রিং রিটার্ন করুন।
"012"-র প্রতিটি ক্যারেক্টার c এর জন্য:
- যদি c == last হয়, তবে পরবর্তী ইটারেশনে যান।
- যদি k < 2^(s-1) হয়, তবে c + solve(s-1, k, c) রিটার্ন করুন।
- k := k - 2^(s-1)
খালি স্ট্রিং রিটার্ন করুন।
মূল মেথড থেকে solve(n, k, None) কল করুন।

উদাহরণ কোড

class Solution:
    def solve(self, s, k, last=None):
        if s == 0:
            return ""
        for c in "012":
            if c == last:
                continue
            if k < 2 ** (s - 1):
                return c + self.solve(s - 1, k, c)
            k -= 2 ** (s - 1)
        return ""

ob = Solution()
n = 4
k = 2
print(ob.solve(n, k))

ইনপুট

4, 2

আউটপুট