{x}
blog image

Add Strings

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 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 <= 104
  • num1 and num2 consist of only digits.
  • num1 and num2 don't have any leading zeros except for the zero itself.

Solution Explanation: Adding Strings

This problem requires adding two non-negative integers represented as strings without using built-in large integer libraries or direct integer conversion. The optimal approach is a simulation of manual addition, using a technique similar to how we add numbers on paper.

Approach: Two Pointers (or Iterators)

  1. Initialization:

    • Two pointers (or iterators), i and j, are initialized to point to the last characters (least significant digits) of num1 and num2, respectively.
    • A variable carry is initialized to 0. This will store the carry-over digit from each addition step.
    • An empty list or string ans is created to store the result.

  2. Iteration:

    • The loop continues as long as either i or j hasn't reached the beginning of their respective strings, or if there's a remaining carry.
    • In each iteration:
      • The digits a and b are extracted from num1 and num2 at positions i and j, respectively. Handle cases where i or j goes out of bounds (meaning we've processed all digits of one string) by setting a or b to 0.
      • The sum a + b + carry is calculated.
      • The units digit of the sum (sum % 10) is appended to ans.
      • The carry-over digit (sum / 10) is updated for the next iteration.
      • Pointers i and j are decremented to move to the next digits.

  3. Result:

    • After the loop, if there's a remaining carry, it's appended to ans.
    • The ans list or string is reversed (because we processed digits from right to left), and the reversed result is converted to a string.

Time and Space Complexity

  • Time Complexity: O(max(m, n)), where m and n are the lengths of num1 and num2. This is because we iterate through the strings at most once.
  • Space Complexity: O(max(m, n)) in the worst case, to store the result. This could be considered O(1) if we are allowed to modify the input strings directly, but this is generally not the case.

Code Examples (Python, Java, C++, Go, TypeScript, Rust, Javascript, Kotlin)

The code examples in various languages provided in the original response accurately reflect this approach. They all follow the same basic algorithm described above, differing only in syntax and data structure usage. For instance:

  • Python: Uses lists for ans for easier manipulation.
  • Java: Uses StringBuilder for efficient string manipulation.
  • C++: Uses std::string and its methods.
  • Go: Uses byte slices and string conversions.
  • TypeScript: Uses number arrays for ans.
  • Rust: Uses Vec<String> for ans and iterators.
  • Javascript: Uses arrays for ans.
  • Kotlin: Uses MutableList<Int> for ans.

All the codes achieve the same functionality; choose the one that's most familiar to you. The comments and variable names within each example code snippet should clarify the steps involved.