দেওয়া start এবং end। অনুমোদিত অপারেশন: ১) ১ বিয়োগ, ২) ২ দিয়ে গুণ। start-কে end-এ কনভার্ট করার ন্যূনতম অপারেশন সংখ্যা বের করতে হবে।
উদাহরণ: start=2, end=7 → ২×২=৪, ৪×২=৮, ৮-১=৭ → ৩ অপারেশন।
রিভার্স গ্রিডি সমাধান (এন্ড থেকে স্ট্রার্টে)
end-কে start-এ রিডিউস করা সহজ কারণ:
- যদি
end <= start: শুধুstart - endবার ডিক্রিমেন্ট করলেই হবে। - যদি
endবিজোড়:end += 1(রিভার্স অফ ডিক্রিমেন্ট)। - যদি
endজোড়:end //= 2(রিভার্স অফ মাল্টিপ্লাই)।
পাইথন কোড
class Solution:
def solve(self, start, end):
ans = 0
while True:
if end <= start:
return ans + start - end
elif end % 2:
end += 1
ans += 1
else:
end //= 2
ans += 1
ob1 = Solution()
print(ob1.solve(2, 7)) # 3
টাইম কমপ্লেক্সিটি: O(log end), স্পেস: O(1)। এটি লিটকোড "Broken Calculator" সমস্যার সমাধান।
