পাইথনে ব্রোকেন ক্যালকুলেটর সমস্যা

মনে করুন আমাদের একটি ব্রোকেন ক্যালকুলেটর আছে যার ডিসপ্লেয়ে একটি সংখ্যা দেখাচ্ছে। আমরা শুধু দুটি অপারেশন করতে পারি:

• ডাবল (Double) — এটি ডিসপ্লেয়ের সংখ্যাকে ২ দিয়ে গুণ করবে।

• ডিক্রিমেন্ট (Decrement) — এটি দেখানো সংখ্যাকে ১ কমাবে।

প্রাথমিকভাবে ক্যালকুলেটর X সংখ্যা দেখাচ্ছে। আমাদের ন্যূনতম কতগুলো অপারেশন দিয়ে Y সংখ্যা দেখাতে হবে সেটি বের করতে হবে।

ইনপুট যদি X = 5 এবং Y = 8 হয়, তবে আউটপুট হবে 2, কারণ একবার ডিক্রিমেন্ট করে ৪ করুন, তারপর ডাবল করে ৮।

এটি সমাধান করতে আমরা নিচের ধাপগুলো ফলো করব (লালচী পদ্ধতি / Greedy - Y থেকে X-এ যাওয়া):

• res := 0

• while Y > X:

  • res += Y % 2 + 1

  • Y := Y // 2 if Y % 2 == 0 else (Y + 1) // 2

• return res + X - Y

উদাহরণ (Python)

নিচের ইমপ্লিমেন্টেশন দেখুন ভালো বুঝতে।

class Solution(object):
    def brokenCalc(self, X, Y):
        res = 0
        while Y > X:
            res += Y % 2 + 1
            Y = Y // 2 if Y % 2 == 0 else (Y + 1) // 2
        return res + X - Y

ob = Solution()
print(ob.brokenCalc(5, 8))

ইনপুট

5 8

আউটপুট

2