पायथन में समीकरण को ठीक करने के लिए आवश्यक सुधारों की संख्या ज्ञात करने का प्रोग्राम

मान लीजिए हमारे पास एक स्ट्रिंग s है जो x+y=z रूप के समीकरण को दर्शाती है। हमें उन न्यूनतम अंकों की संख्या ज्ञात करनी है जिन्हें हमें s में जोड़ने की आवश्यकता है ताकि समीकरण सत्य हो जाए।

इसलिए, यदि इनपुट s = '2+6=7' जैसा है, तो आउटपुट 2 होगा।

हम समीकरण को "21+6=27" में बदल सकते हैं "1" और "2" डालकर। तो आवश्यक सुधारों की कुल संख्या 2 है।

हल करने के चरण

s को "+" वर्ण के आधार पर भागों में विभाजित करें, बाएं भाग को A में और दाएं भाग को rest में रखें
rest को "=" वर्ण के आधार पर भागों में विभाजित करें, बाएं भाग को B में और दाएं भाग को C में रखें
dp(A का आकार - 1, B का आकार - 1, C का आकार - 1, 0) लौटाएं
dp() फ़ंक्शन परिभाषित करें। यह i, j, k, carry लेगा
- यदि i <= -1 और j <= -1 और k <= -1, तो
  - यदि carry, 0 के समान है तो 0 लौटाएं अन्यथा 1
- last1 := (A[i]) यदि i >= 0 अन्यथा 0
- last2 := (B[j]) यदि j >= 0 अन्यथा 0
- last3 := (C[k]) यदि k >= 0 अन्यथा 0
- prefix1 := (A[इंडेक्स 0 से i + 1 तक]) यदि i >= 0 अन्यथा 0
- prefix2 := (B[इंडेक्स 0 से j + 1 तक]) यदि j >= 0 अन्यथा 0
- prefix3 := (C[इंडेक्स 0 से k + 1 तक]) यदि k >= 0 अन्यथा 0
- यदि i <= -1 और j <= -1, तो
  - rhs := prefix3 - carry
  - यदि rhs <= 0, तो |rhs| लौटाएं
  - यदि i, -1 के समान है या j, -1 के समान है, तो str(rhs) का आकार लौटाएं
  - अन्यथा, False लौटाएं
- यदि k <= -1, तो str(prefix1 + prefix2 + carry) का आकार लौटाएं
- ans := infinity
- carry2, lhs := (carry + last1 + last2) को 10 से विभाजित करने पर भागफल और शेषफल
- यदि lhs, last3 के समान है, तो ans := dp(i - 1, j - 1, k - 1, carry2)
- req := last3 - carry - last2
- extra_zeros := 0 और -1 - i का अधिकतम
- carry2 := 1 यदि req < 0 अन्यथा 0
- ans := ans और 1 + extra_zeros + dp(max(-1, i), j - 1, k - 1, carry2) का न्यूनतम
- req := last3 - carry - last1
- extra_zeros := 0 और -1 - j का अधिकतम
- carry2 := 1 यदि req < 0 अन्यथा 0
- ans = ans और 1 + extra_zeros + dp(i - 1, max(-1, j), k - 1, carry2) का न्यूनतम
- carry2, lhs := (last1 + last2 + carry) को 10 से विभाजित करने पर भागफल और शेषफल
- ans := ans और 1 + dp(i - 1, j - 1, k, carry2) का न्यूनतम
- ans लौटाएं
मुख्य विधि से dp(A का आकार - 1, B का आकार - 1, C का आकार - 1, 0) लौटाएं

उदाहरण

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'