Add Strings

Problem Statement

The challenge presented requires adding two non-negative integers that are given as string representations and returning the result as a string. This must be accomplished without converting the strings directly to integer data types or utilizing any library designed to handle large integers such as BigInteger. The solution demands a more fundamental approach to addition, likely necessitating an algorithm similar to how manual addition is performed, digit by digit, while managing carry-over values across digit boundaries.

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

Approach and Intuition

To sum two large numbers represented as strings without converting them directly into integers, we simulate the traditional column-by-column addition method taught in basic arithmetic. The process follows these logical steps:

1. Initialize an empty result string and a variable to keep track of carry.
2. Align the strings by their rightmost digits. This may involve padding the shorter string with leading zeros.
3. Iterate through the digits of both strings from right to left (i.e., from least significant digit to most significant digit):
   • Sum the digits at the current position along with any carry from the previous position.
   • Compute the digit of the result by taking the modulo of the sum by 10.
   • Update the carry for the next iteration as the division of the sum by 10.
4. After processing both strings, check if there is any remaining carry and, if so, append it to the result.
5. Since the result has been built from the least significant to the most significant digit, reverse the result string before returning it to get the correct order.

Considerations Based on Constraints:

• The lengths of both strings can vary widely, so the solution should cater to the situation where one string is significantly shorter than the other.
• Only digits are involved; therefore, no checks for illegal characters are required.
• We do not have to handle negative numbers or decimals, simplifying our task slightly.
• Solutions must handle arbitrary large lengths efficiently since the upper constraint allows for strings of length up to 104.

Through this method, we efficiently handle the addition of two arbitrary-length numbers represented as strings, respecting the constraints and requirements set forth.

Solutions

class Solution {
    public String concatenateNumbers(String number1, String number2) {
        StringBuilder resultBuilder = new StringBuilder();
            
        int carryOver = 0;
        int index1 = number1.length() - 1;
        int index2 = number2.length() - 1;
            
        while (index1 >= 0 || index2 >= 0) {
            int digit1 = index1 >= 0 ? number1.charAt(index1) - '0' : 0;
            int digit2 = index2 >= 0 ? number2.charAt(index2) - '0' : 0;
            int sum = (digit1 + digit2 + carryOver) % 10;
            carryOver = (digit1 + digit2 + carryOver) / 10;
            resultBuilder.append(sum);
            index1--;
            index2--;
        }
            
        if (carryOver != 0)
            resultBuilder.append(carryOver);
            
        return resultBuilder.reverse().toString();
    }
}