পাইথনে নির্দিষ্ট দৈর্ঘ্যের আপসাইড-ডাউন নাম্বার খুঁজে বের করা

আপসাইড-ডাউন নাম্বার: ১৮০ ডিগ্রি ঘুরালে একই দেখতে পাওয়া সংখ্যা (যেমন: 0, 1, 8, 6↔9)।

দেওয়া দৈর্ঘ্য n এর জন্য সব সম্ভব আপসাইড-ডাউন নাম্বার বের করতে হবে। উদাহরণ: n=2 → ['11', '69', '88', '96']।

রিকার্সিভ সমাধান

middle(x) ফাংশন দিয়ে মাঝপথের সংখ্যাগুলো বের করা হয়, তারপর দুই পাশে বৈধ ডিজিট জোড়া যোগ করা হয়।

• বেস কেস: x=0 → [""], x=1 → ['0','1','8']
• রিকার্সিভ স্টেপ: middle(x-2) থেকে প্রতিটি মাঝপথের জন্য 0..0, 1..1, 6..9, 8..8, 9..6 জোড়া যোগ করা হয়।
• শেষে n দৈর্ঘ্যের জন্য ফলাফল সর্ট করে রিটার্ন।

পাইথন কোড

class Solution:
    def solve(self, n):
        if not n:
            return []
        def middle(x):
            if not x:
                return [""]
            if x == 1:
                return list("018")
            ret = []
            mid = middle(x - 2)
            for m in mid:
                if x != n:  # লিডিং জিরো এড়াতে
                    ret.append("0" + m + "0")
                ret.append("1" + m + "1")
                ret.append("6" + m + "9")
                ret.append("8" + m + "8")
                ret.append("9" + m + "6")
            return ret
        return sorted(middle(n))

ob = Solution()
print(ob.solve(2))  # ['11', '69', '88', '96']

টাইম কমপ্লেক্সিটি: O(5^(n/2)), স্পেস: O(5^(n/2))।