Codewars: Sum Strings

Question

Sum Strings

Codewars kata.

It's supposed to be able to handle big integers.

 

Question

Given the string representations of two integers, return the string representation of the sum of those integers.

For example:

sumStrings('1','2') // => '3'

A string representation of an integer will contain no characters besides the ten numerals "0" to "9".

 

Solution

"use strict";
const reverseArr = s => s.split("").reverse();

function sumStrings(a, b) {
   [a, b] = [reverseArr(a), reverseArr(b)];
   let carry = 0;
   const arr = []
   const [mx, mn] = (a.length >= b.length) ? [a, b] : [b, a];
   mx.forEach((itm, idx) => {
      let sm = Number(itm) + (Number(mn[idx]) || 0) + carry;
      [sm, carry] = sm > 9 ? [sm%10, 1] : [sm, 0];
      arr.unshift(sm)
   })
   if (carry) arr.unshift(carry);
   return arr.join("").replace(/^(0+)/, "");
}

Answer 1

JavaScript style

• Delimit cod blocks with {}. Eg if (foo) bar = 0; should be if (foo) { bar = 0; }

• Use semicolons consistently!

• Avoid Array.unshift as it is much slower than Array.push. If you know the size of the array pre-allocate the array new Array(size) and then pput items on the array via an index. (See example)

• Be wary of destructuring as it can sometimes be rather slow (engines converting the right side to array (like) before assigning to the left). As destructuring becomes more main stream and JS engines stabilize new features destructuring has and will continue to improve in terms of performance.

Complexity.

Your function is too complex!

The complexity of this function is \$O(n)\$ where \$n\$ is the number of digits in the result. A well written function should thus have a performance that is related linearly to \$n\$ however your functions performance does not have this relationship, demonstrating a logarithmic performance (approx) \$O(n^2)\$ making it very slow for large numbers.

The reason is your use of Array.unshift. Each time you unshift a value to the array each item on the array needs to be moved up by one item. This is compounded every time the array size doubles as jS will then create a new array, and copy all the items to that array. As JS is a managed environment and memory is not cleaned up until the function exits or is forced by low memory your function not only has high time complexity but on theoretically infinite memory machines also has a storage complexity of \$O(n^2)\$

Rewrites

The rewrites are both \$O(n)\$ time and space complex, where \$n\$ is number of digits in the result (including leading zeros).

rather than revers the digits the code pre-allocates the result array with the required number of digits and then works from the least significant digit up.

Note that when the index into the strings a or b is less than 0 the coercion forced by the bitwise OR 0 | 0 will convert undefined to the number 0.

Ignoring leading zeros (assumes that there are no leading zeros for values over 0)

"use strict";
function sumStrings(a, b) {
    var carry = 0, i = a.length, j = b.length, k = i > j ? i : j;
    const res = new Array(k);
    while (i > 0 || j > 0) {
        const sum = (a[--i] | 0) + (b[--j] | 0) + carry;
        res[--k] = sum % 10;
        carry = (sum > 9 && 1) || 0;
    }
    return (carry ? carry : "") + res.join("");
}

The next version will accept leading zeros truncating the result string if there is no carry on the last digit. The truncation is at the last non zero digit encountered.

"use strict";
function sumStrings(a, b) {
    var carry = 0, i = a.length, j = b.length, k = i > j ? i : j, lastNonZero = k;
    const res = new Array(k);
    while (i > 0 || j > 0) {
        const sum = (a[--i] | 0) + (b[--j] | 0) + carry;
        lastNonZero = sum ? k : lastNonZero;
        res[--k] = sum % 10;
        carry = (sum > 9 && 1) || 0;
    }
    return carry ? carry + res.join("") : res.join("").slice(lastNonZero -1); 
}

BigInt?

You could also have just parsed the two strings as BigInt but that is not the point of the exercise.

The summing algorithm is a basic component of computing, the algorithm will also work on any number base. Eg Binary base 2 Hex base 16.

With only minor modifications the function will handle any base and never actually add any numbers