Add Strings

Problem Description

Given two non-negative integers, num1 and num2 represented as strings, 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) and must not convert the inputs to integers directly.

Key Insights

• The problem requires simulating the addition of two numbers digit by digit.
• Since the numbers are provided as strings, we will process them from the least significant digit (rightmost) to the most significant digit (leftmost).
• We need to handle carries that occur when the sum of two digits exceeds 9.
• The final result should be constructed in reverse order, as we will be calculating from the least significant to the most significant digit.

Space and Time Complexity

Time Complexity: O(max(n, m)), where n and m are the lengths of num1 and num2 respectively.
Space Complexity: O(max(n, m)), for storing the result.

Solution

To solve the problem, we will:

1. Initialize pointers for both strings starting from the end (least significant digits).
2. Use a carry variable to keep track of any carry-over from the addition of two digits.
3. Iterate through both strings until both are fully processed.
4. For each digit, convert the character to an integer, calculate the sum including carry, and determine the new digit and carry.
5. Append the result digit to a list.
6. Finally, reverse the list to get the correct order of digits and convert it to a string.

Code Solutions