পাইথনে সমীকরণ ঠিক করার জন্য ন্যূনতম ডিজিট যোগ করার সংখ্যা বের করা

একটি স্ট্রিং s দেওয়া আছে যা x+y=z ফরম্যাটের একটি সমীকরণ রিপ্রেজেন্ট করে। সমীকরণ সঠিক করার জন্য ন্যূনতম কতটি ডিজিট যোগ করতে হবে তা বের করতে হবে।

উদাহরণ: s = '2+6=7' → আউটপুট 2। কারণ "21+6=27" বানাতে '1' এবং '2' যোগ করা লাগে।

সমাধানের ধাপসমূহ (DP on Digits with Carry)

s-কে '+' দিয়ে স্প্লিট করে A (লেফট) এবং rest পান। rest-কে '=' দিয়ে স্প্লিট করে B এবং C পান।
dp(i, j, k, carry) ফাংশন ডিফাইন করুন যেখানে i,j,k হলো A,B,C-র ইনডেক্স (রাইট টু লেফট) এবং carry হলো ক্যারি।
বেস কেস: সব ইনডেক্স -১ এবং ক্যারি ০ হলে ০, ক্যারি ১ হলে ১।
প্রতিটি ডিজিট পজিশনে বর্তমান ডিজিট ও প্রিফিক্স নম্বর বিবেচনা করে সব সম্ভাব্য ইনসার্শন ট্রাই করুন (A-তে ডিজিট, B-তে ডিজিট, C-তে ডিজিট) এবং ন্যূনতম ইনসার্শন কাউন্ট করুন।
মেমোরাইজেশন বা রিকার্সিভ DP দিয়ে সমাধান করুন।

পাইথন কোড উদাহরণ

class Solution:
    def solve(self, s):
        A, rest = s.split("+")
        B, C = rest.split("=")
        def dp(i, j, k, carry):
            if i <= -1 and j <= -1 and k <= -1:
                return 0 if carry == 0 else 1
            last1 = int(A[i]) if i >= 0 else 0
            last2 = int(B[j]) if j >= 0 else 0
            last3 = int(C[k]) if k >= 0 else 0
            prefix1 = int(A[:i+1]) if i >= 0 else 0
            prefix2 = int(B[:j+1]) if j >= 0 else 0
            prefix3 = int(C[:k+1]) if k >= 0 else 0
            if i <= -1 and j <= -1:
                rhs = prefix3 - carry
                if rhs <= 0:
                    return abs(rhs)
                if i == -1 or j == -1:
                    return len(str(rhs))
                else:
                    assert False
            if k <= -1:
                return len(str(prefix1 + prefix2 + carry))
            ans = float("inf")
            carry2, lhs = divmod(carry + last1 + last2, 10)
            if lhs == last3:
                ans = dp(i - 1, j - 1, k - 1, carry2)
            req = last3 - carry - last2
            extra_zeros = max(0, -1 - i)
            carry2 = 1 if req < 0 else 0
            ans = min(ans, 1 + extra_zeros + dp(max(-1, i), j - 1, k - 1, carry2))
            req = last3 - carry - last1
            extra_zeros = max(0, -1 - j)
            carry2 = 1 if req < 0 else 0
            ans = min(ans, 1 + extra_zeros + dp(i - 1, max(-1, j), k - 1, carry2))
            carry2, lhs = divmod(last1 + last2 + carry, 10)
            ans = min(ans, 1 + dp(i - 1, j - 1, k, carry2))
            return ans
        return dp(len(A) - 1, len(B) - 1, len(C) - 1, 0)

ob = Solution()
print(ob.solve('2+6=7'))

ইনপুট

'2+6=7'