415. Add Strings

Problem Statement

link: LeetCode.cn LeetCode Given two non-negative integers, num1 and num2 represented as string, return the sum of num1 and num2 as a string.

You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not convert the inputs to integers directly.

Example:

Input: num1 = "11", num2 = "123" Output: 134

Input: num1 = "456", num2 = "77" Output: 533

Input: num1 = "0", num2 = "0" Output: 0

Constraints: 1 <= num1.length, num2.length <= 104 num1 and num2 consist of only digits. num1 and num2 don’t have any leading zeros except for the zero itself.

Solution Approach

The solution simulates the addition of two numbers digit by digit from right to left, managing carry values and building the result string iteratively.

Algorithm

1. Digit-by-Digit Addition: Iterate through the digits of both strings from right to left, adding corresponding digits along with any carry from the previous addition.
2. Carry Management: Calculate the carry by dividing the sum of digits by 10 and update the result string with the remainder of the division.
3. Handle Remaining Carry: After processing all digits, if there’s any remaining carry, prepend it to the result string to form the final sum.

Complexity

time complexity: O(max(len(num1), len(num2))) space complexity: O(max(len(num1), len(num2)))

Implement

    class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        res = ""
        i, j, carry = len(num1) - 1, len(num2) - 1, 0
        while i >= 0 or j >= 0:
            n1 = int(num1[i]) if i >= 0 else 0
            n2 = int(num2[j]) if j >= 0 else 0
            tmp = n1 + n2 + carry
            carry = tmp // 10
            res = str(tmp % 10) + res
            i, j = i - 1, j - 1
        return "1" + res if carry else res

    
    

Twitter  facebook  Email