Problem statement

https://binarysearch.com/problems/Equation-Typo/

Solution

Quite difficult problem, I thought to solve it with bruteforce, where we add no more than 3 digits to each number, but in python (and possibly in other languages) it will give TLE. Let us use dp(i, j, k, carry), where it is the answer how many digits we need to add to make equation A[:i+1] + B[:j+1] + carry == C[:k+1] possible.

The problem is what to do with extra zeroes, imagine the case 3 + 4862 = 26, then we need to go to the negative index -2 to make it 403 + 4862 = 5265.

  1. If i <= -1 and j <= -1 means that digits in A and B are finished, so we need to add digits to number C. If balance is 0 or -1 (it can not be smaller): in fact there can be cases:
    1. When prefix3 = 0, carry = 0, then add nothing, in fact it will be covered i <= -1, j <= -1 and k <= -1.
    2. When prefix3 = 1, carry = 1, then add nothing.
    3. When prefix3 = 0, carry = 1, then in fact k <= -1, so it will be covered later.
    4. Also if we have i == -1 or j == -1, than one number is finished, another is not.

  2. If k <= -1, then it means that number C is finished, so we just need to add digits to either A or B.

  3. If we already have equalty for given place, than we add it to options.
  4. Also we can try to add digit to number A: here we need to deal with case of extra zeroes.
  5. Similar logic for number B.
  6. Final case is to add digit to number C.

Complexity

It is O(n^3), where n is maximum length of A, B, C.

Code

### Code by Awice
class Solution:
    def solve(self, s):
        A, rest = s.split("+")
        B, C = rest.split("=")

        def process(A, i):
            return (int(A[i]), int(A[:i+1])) if i >= 0 else (0, 0)

        @lru_cache(None)
        def dp(i, j, k, carry):
            if i <= -1 and j <= -1 and k <= -1: return int(carry != 0)

            last1, prefix1 = process(A, i)
            last2, prefix2 = process(B, j)
            last3, prefix3 = process(C, k)

            # Nothing LHS
            if i <= -1 and j <= -1:
                rhs = prefix3 - carry
                if -1 <= rhs <= 0:
                    return -rhs
                if i == -1 or j == -1:
                    return len(str(rhs))

            # Nothing RHS
            if k <= -1:
                return len(str(prefix1 + prefix2 + carry))

            ans = float("inf")
            # Don't add anything
            carry2, lhs = divmod(carry + last1 + last2, 10)
            if lhs == last3:
                ans = dp(i - 1, j - 1, k - 1, carry2)

            # Add to end of A
            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))

            # Add to end of B
            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))

            # Add to end of C
            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)