Adding Strings#

Given two non-negative integers num1 and num2 in string form, calculate their sum.
Note:

• The length of num1 and num2 are both less than 5100.
• num1 and num2 only contain numbers 0-9.
• num1 and num2 do not contain any leading zeros.
• You cannot use any built-in BigInteger library, nor can you directly convert the input strings into integer form.

Example#

Solution#

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var addStrings = function(num1, num2) {
    var diff = Array(Math.abs(num1.length - num2.length)).fill(0).join("");
    if(num1.length > num2.length) num2 = diff + num2;
    else num1 = diff + num1;
    var target = "";
    var n = num1.length;
    var carry = 0;
    for(let i=n-1; i>=0; --i){
        let num = ~~(num1[i]) + ~~(num2[i]) + carry;
        if(num >= 10) {
            carry = 1;
            num -= 10;
        }else{
            carry = 0;
        }
        target = num + target;
    }
    if(carry) target = "1" + target;
    return target;
};

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var addStrings = function(num1, num2) {
    var p1 = num1.length-1;
    var p2 = num2.length-1;
    var target = "";
    var carry = 0;
    while(p1>=0 || p2>=0 || carry!==0){
        if(p1>=0) carry += ~~(num1[p1--]);
        if(p2>=0) carry += ~~(num2[p2--]);
        target = (carry%10) + target;
        carry = ~~(carry / 10);
    }
    return target;
};

Idea#

My initial idea was to pad 0 to align the numbers, then add each digit from right to left. Use carry as the carry flag and target as the target string. After padding with 0, go through the loop, convert each character of the two strings to int, add them with the carry, check if the sum is greater than 10 for carry, and concatenate the result to the target string. If there is a carry at the end, append 1 to the target string. Later, using the double pointer approach, the code becomes more concise. Again, use carry as the carry flag and the increment value, and target as the target string. No need to pad with 0 for alignment, the loop condition is satisfied if either of the two pointers is greater than or equal to 0, or if there is a carry. Determine whether to add its value to the increment carry by checking if the pointer value is greater than or equal to 0, then concatenate the modulo of the increment to the target string, take the increment divided by 10 as the carry flag, and finally return the target string.

Daily Question#

Reference#