Difficulty: Easy | Acceptance: 52.20% | Paid: No Topics: Math, String, Simulation
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.
- Examples
- Constraints
- Digit-by-Digit Addition (Two Pointers)
- Recursive Approach
- [Padding and Addition]((#padding-and-addition)
Examples
Example 1:
Input: num1 = "11", num2 = "123"
Output: "134"
Example 2:
Input: num1 = "456", num2 = "77"
Output: "533"
Example 3:
Input: num1 = "0", num2 = "0"
Output: "0"
Constraints
1 <= num1.length, num2.length <= 10^4
num1 and num2 consist of only digits.
num1 and num2 do not contain any leading zeros except for the zero itself.
Digit-by-Digit Addition (Two Pointers)
Intuition Simulate manual addition by processing digits from right to left, maintaining a carry value, and building the result string.
Steps
- Initialize two pointers at the end of both strings and a carry variable
- Loop while either pointer is valid or carry exists
- Extract digits (0 if pointer is out of bounds), sum them with carry
- Append the remainder to result and update carry
- Reverse the result and return
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
i, j = len(num1) - 1, len(num2) - 1
carry = 0
result = []
while i >= 0 or j >= 0 or carry:
digit1 = int(num1[i]) if i >= 0 else 0
digit2 = int(num2[j]) if j >= 0 else 0
total = digit1 + digit2 + carry
carry = total // 10
result.append(str(total % 10))
i -= 1
j -= 1
return ''.join(reversed(result))Complexity
- Time: O(max(m, n)) where m and n are lengths of input strings
- Space: O(max(m, n)) for the result string
- Notes: Most efficient approach with minimal operations
Recursive Approach
Intuition Use recursion to process digits from right to left, building the result string through recursive calls.
Steps
- Base case: when both pointers are out of bounds and carry is 0, return empty string
- Get current digits (0 if pointer out of bounds), calculate sum and new carry
- Recursively process remaining digits and append current digit
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
def helper(i: int, j: int, carry: int) -> str:
if i < 0 and j < 0 and carry == 0:
return ""
digit1 = int(num1[i]) if i >= 0 else 0
digit2 = int(num2[j]) if j >= 0 else 0
total = digit1 + digit2 + carry
new_carry = total // 10
return helper(i - 1, j - 1, new_carry) + str(total % 10)
return helper(len(num1) - 1, len(num2) - 1, 0)Complexity
- Time: O(max(m, n)) where m and n are lengths of input strings
- Space: O(max(m, n)) for recursion stack
- Notes: Elegant but may cause stack overflow for very large inputs
Padding and Addition
Intuition Pad the shorter string with leading zeros to make both strings equal length, then add digit by digit.
Steps
- Find the maximum length of both strings
- Pad the shorter string with leading zeros
- Iterate from right to left, adding corresponding digits
- Handle final carry if present
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
max_len = max(len(num1), len(num2))
num1 = num1.zfill(max_len)
num2 = num2.zfill(max_len)
carry = 0
result = []
for i in range(max_len - 1, -1, -1):
digit1 = ord(num1[i]) - ord('0')
digit2 = ord(num2[i]) - ord('0')
total = digit1 + digit2 + carry
carry = total // 10
result.append(str(total % 10))
if carry:
result.append(str(carry))
return ''.join(reversed(result))Complexity
- Time: O(max(m, n)) where m and n are lengths of input strings
- Space: O(max(m, n)) for the result string
- Notes: Simpler logic but uses extra space for padding