#415

Easy

LeetCode Problem Workspace

Add Strings

Given two non-negative integers as strings, sum them and return the result as a string without converting to integers directly.

math string simulation

Problem Statement

You are given two non-negative integers, num1 and num2, represented as strings. Your goal is to return the sum of num1 and num2 as a string.

You are required to solve this problem without converting the strings into integers or using any built-in libraries designed for handling large integers. The solution must involve simulating the addition process manually, as done by hand.

Examples

Example 1

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

Output: "134"

Example details omitted.

Example 2

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

Output: "533"

Example details omitted.

Example 3

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

Output: "0"

Example details omitted.

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

Simulating Addition

Start by adding the digits from the least significant digit (rightmost) to the most significant digit (leftmost). For each position, handle the carry from the previous addition.

Iterating Over the Strings

Iterate over the two strings from the end to the beginning. For each digit, convert the character to an integer, add the corresponding digits along with any carry, and store the result as a string.

Handling Carries

If the sum of digits is greater than or equal to 10, carry over the 1 to the next higher digit. Continue this process until all digits are processed, appending the final carry if necessary.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(max(m, n)), where m and n are the lengths of the two input strings. Space complexity is O(max(m, n)) for storing the result string.

What Interviewers Usually Probe

Tests your ability to simulate arithmetic operations without using built-in integer conversion.
Evaluates your understanding of string manipulation and handling of carries in addition.
Checks if you can handle edge cases like different string lengths and no leading zeros.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly handle carries, especially at the most significant digit.
Not considering edge cases like one string being longer than the other.
Incorrectly managing the case when the result has an additional carry at the end.

Follow-up variants

Add Strings for large numbers where the length of the strings exceeds typical integer limits.
Modify the problem to add multiple strings, not just two.
Optimize the solution to handle cases where both strings are of equal length.

FAQ

What is the main challenge in the Add Strings problem?

The main challenge is simulating the addition process without using integer conversion and handling carries correctly between digits.

How do I handle strings of different lengths in Add Strings?

You should align both strings from the right end, treating the shorter string as if it has leading zeros. Add digit-by-digit and manage carries.

Can I use built-in libraries for big integers in the Add Strings problem?

No, you must solve the problem without converting strings to integers or using libraries designed for handling large numbers.

How does GhostInterview help with Add Strings?

GhostInterview helps by offering step-by-step guidance on simulating the addition process, focusing on string manipulation and carry handling.

What is the expected time complexity for Add Strings?

The time complexity is O(max(m, n)), where m and n are the lengths of the two input strings, as you process each character of the strings once.

terminal

Solution

Solution 1: Two Pointers

We use two pointers $i$ and $j$ to point to the end of the two strings respectively, and start adding bit by bit from the end. Each time we take out the corresponding digits $a$ and $b$, calculate their sum $a + b + c$, where $c$ represents the carry from the last addition. Finally, we append the units digit of $a + b + c$ to the end of the answer string, and then take the tens digit of $a + b + c$ as the value of the carry $c$, and loop this process until the pointers of both strings have pointed to the beginning of the string and the value of the carry $c$ is $0$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        i, j = len(num1) - 1, len(num2) - 1
        ans = []
        c = 0
        while i >= 0 or j >= 0 or c:
            a = 0 if i < 0 else int(num1[i])
            b = 0 if j < 0 else int(num2[j])
            c, v = divmod(a + b + c, 10)
            ans.append(str(v))
            i, j = i - 1, j - 1
        return "".join(ans[::-1])

    def subStrings(self, num1: str, num2: str) -> str:
        m, n = len(num1), len(num2)
        neg = m < n or (m == n and num1 < num2)
        if neg:
            num1, num2 = num2, num1
        i, j = len(num1) - 1, len(num2) - 1
        ans = []
        c = 0
        while i >= 0:
            c = int(num1[i]) - c - (0 if j < 0 else int(num2[j]))
            ans.append(str((c + 10) % 10))
            c = 1 if c < 0 else 0
            i, j = i - 1, j - 1
        while len(ans) > 1 and ans[-1] == '0':
            ans.pop()
        if neg:
            ans.append('-')
        return ''.join(ans[::-1])

Continue Practicing

#412 fizz buzz #537 complex number multiplication #592 fraction addition and subtraction