Add Strings

Problem

Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

• The length of both num1 and num2 is < 5100.
• Both num1 and num2 contains only digits 0-9.
• Both num1 and num2 does not contain any leading zero.
• You must not use any built-in BigInteger library or convert the inputs to integer directly.

Solution

public class Solution {
    public String addStrings(String num1, String num2) {
        StringBuilder sb = new StringBuilder();
        int carry = 0;
        for (int i = num1.length() - 1, j = num2.length() - 1; i >= 0 || j >= 0 || carry != 0; i--, j--) {
            int a = i < 0 ? 0 : num1.charAt(i) - '0';
            int b = j < 0 ? 0 : num2.charAt(j) - '0';
            sb.append((a + b + carry) % 10);
            carry = (a + b + carry) / 10;
        }
        return sb.reverse().toString();
    }
}

Analysis

We are not allowed to use any built-in parse() method, neither converting the input to int
Therefore, we use a loop and two pointers i and j to go through each digit of input
We also have a var carry to manipulate the adding procedure
I was asked about this question on my first Google phone interview
After I giving out this solution, I was asked to consider the negative input as well
We just need to get the negative sign out then compute the positive input and add the negative sign back at the end

Complexity:

• Time: O(n), where n is the larger length of num1 and num2
• Space: O(n), where n represents same above because of using StringBuilder