algoadvance

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

Since you cannot use any built-in methods or convert the inputs directly into integers, you need to simulate the addition of the two numbers digit by digit.

Clarifying Questions

1. Q: Can the input strings contain leading zeros? A: Yes, but the strings will only contain digits 0-9 and might have leading zeros.

2. Q: What is the maximum length of the input strings? A: The length of the input strings can be up to 10,000 characters.

Strategy

1. Initialization:
   • Two pointers starting at the end of the two strings (least significant digits).
   • A variable to handle carry over.
   • A result list to store the sum digits.
2. Simulation of Addition:
   • Traverse both strings from the end to the beginning.
   • For each pair of digits (and carry), calculate the sum and determine the new carry.
   • Append the result of the sum (modulo 10) to the result list.
3. Final Steps:
   • If there is a remaining carry after the loop, append it to the result list.
   • Reverse the result list and convert it to a string.

Code

Here is a Python implementation using the above strategy:

def addStrings(num1: str, num2: str) -> str:
    # Initialize pointers for num1 and num2
    i, j = len(num1) - 1, len(num2) - 1
    
    # Initialize carry and the result list
    carry = 0
    result = []
    
    # Loop until both pointers are exhausted and there is no carry
    while i >= 0 or j >= 0 or carry:
        # Get current digit from num1 or 0 if pointer is exhausted
        x1 = ord(num1[i]) - ord('0') if i >= 0 else 0
        # Get current digit from num2 or 0 if pointer is exhausted
        x2 = ord(num2[j]) - ord('0') if j >= 0 else 0
        
        # Calculate the sum of the digits plus the carry
        value = x1 + x2 + carry
        
        # Update carry
        carry = value // 10
        
        # Append the current digit to the result list
        result.append(value % 10)
        
        # Move the pointers
        i -= 1
        j -= 1
    
    # The result list will have the digits of the sum in reverse order
    return ''.join(str(x) for x in reversed(result))

Time Complexity

• O(n + m): Where n is the length of num1 and m is the length of num2. We traverse both strings once, and the reversing step also takes linear time.

Space Complexity

• O(max(n, m)): The result list will store each digit of the sum. The length of this list is at most the length of the longer input string plus one in case of an extra carry.

This solution ensures the addition of the strings in a manner similar to the way you would do it manually on paper.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?