algoadvance

Leetcode 415. Add Strings

Problem Statement

You are given two non-negative integers represented as string num1 and num2, 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 Python’s int) and without converting the inputs to integers directly.

Clarifying Questions

  1. Input Range: What is the maximum length for the input strings?
    • Response: The input strings can be very large, up to (10^4) digits.
  2. Leading Zeros: Can the input strings contain leading zeros?
    • Response: Yes, but the answer should not contain leading zeros, except when the answer is “0”.
  3. Character Set: Are the input strings guaranteed to only contain digits (0-9)?
    • Response: Yes, the input strings will only contain digits.

Strategy

To solve this problem, we can use the elementary school addition method but performed on strings. Here is a step-by-step breakdown of the approach:

  1. Append Zeros for Equal Length: To make the addition easier, start by appending leading zeros to the shorter string so that both strings have the same length. This simplifies the digit-wise addition as we won’t run into out-of-bound issues.

  2. Addition from Right to Left: Perform the addition from the rightmost end (least significant digit) to the leftmost end (most significant digit). Keep track of the carry for each step.

  3. Construct Result: Append the result of each digit’s addition to the result string. Finally, if there’s any carry left after the final addition, append it to the result.

  4. Edge Cases: Ensure to handle cases where the strings have vastly different lengths and when there is an overflow carry at the final step.

Code

Here’s the C++ implementation of the above strategy:

#include <iostream>
#include <string>
#include <algorithm>

std::string addStrings(std::string num1, std::string num2) {
    int n1 = num1.size();
    int n2 = num2.size();
    int maxLength = std::max(n1, n2);
    
    // Pad the shorter string with leading zeros
    if (n1 < maxLength) {
        num1.insert(num1.begin(), maxLength - n1, '0');
    } else if (n2 < maxLength) {
        num2.insert(num2.begin(), maxLength - n2, '0');
    }
    
    std::string result;
    int carry = 0;
    
    // Perform addition from right to left
    for (int i = maxLength - 1; i >= 0; --i) {
        int digit1 = num1[i] - '0';
        int digit2 = num2[i] - '0';
        
        int sum = digit1 + digit2 + carry;
        carry = sum / 10;
        int current_digit = sum % 10;
        
        result.push_back(current_digit + '0');
    }
    
    if (carry > 0) {
        result.push_back(carry + '0');
    }
    
    // The result is in reverse order
    std::reverse(result.begin(), result.end());
    
    return result;
}

int main() {
    std::string num1 = "456";
    std::string num2 = "77";
    std::cout << "Sum: " << addStrings(num1, num2) << std::endl; // 533
    return 0;
}

Time Complexity

The time complexity of this solution is O(max(N, M)), where (N) and (M) are the lengths of num1 and num2, respectively. This is because we are processing each digit of both strings exactly once. Additionally, the space complexity is also O(max(N, M)) due to the storage of the result string and padding of the shorter string.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI