Sum of two numbers in array

Question

The task

You are given two non-empty arrays representing two non-negative integers. The digits are stored in reverse order and each of their items contain a single digit. Add the two numbers and return it as an array.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example: Input: [2,4,3] + [5,6,4] Output: [7,0,8]

const a1 = [2,4,3]; const a2 = [5,6,4]; 

My imperative solution

function addTwoNumbers(a1, a2) { const len = a1.length > a2.length ? a1.length : a2.length; const res = []; let memo = 0; const sanitize = n => n ? n : 0; for (let i = 0; i < len; i++) { let sum = sanitize(a1[i]) + sanitize(a2[i]) + memo; memo = sum > 9 ? sum % 9 : 0; sum = sum > 9 ? sum % 10 : sum; res.push(sum); } return res; } console.log(addTwoNumbers(a1, a2)); 

My functional solution

const range = num => Array.from(new Array(num), (_, i) => i); const addTwoNumbers2 = (a1, a2) => { const sanitize = n => n ? n : 0; const len = a1.length > a2.length ? a1.length : a2.length; const {res} = range(len) .reduce((acc,i) => { let sum = sanitize(a1[i]) + sanitize(a2[i]) + acc.memo; acc.memo = sum > 9 ? sum % 9 : 0; sum = sum > 9 ? sum % 10 : sum; acc.res.push(sum); return acc; }, {res: [], memo: 0,}); return res; }; console.log(addTwoNumbers2(a1, a2)); 

Answer 1

Bug

Unfortunately both your functions return bad results for many input arguments. You don't carry.

Both should return [0,1] however they return [0]

addTwoNumbers([1], [9]); // >> [0] wrong addTwoNumbers2([1], [9]); // >> [0] wrong 

And the return for the following should be [6,0,1] but they return [6,6]

addTwoNumbers([9], [7, 9]); // >> [6, 6] wrong addTwoNumbers2([9], [7, 9]); // >> [6, 6] wrong 

The reason is that you forget to deal with the carry.

To number?

Konijn's answer is a tempting solution but will also fail as it is limited by JS Number.

addTwoNumbers([1,1,9,9,0,4,7,4,5,2,9,9,1,7,0,0,9], [1,9,9,0,4,7,4,5,2,9,9,1,7,0,0,9]) 

The correct answer is

[2,0,9,0,5,1,2,0,8,1,9,1,9,7,0,9,9]

However Konijn's solution incorrectly returns.

[0,0,9,0,5,1,2,0,8,1,9,1,9,7,0,9,9]

This is because the second number is Number.MAX_SAFE_INTEGER above which you can not get a reliable result.

BigInt

You could use a BigInt as its size is not limited.

Big ints can be written with the suffix n

 const big = 9907919180215090099079191802150900n; // Note the suffix n 

To convert the reversed number to a big int

 const a = [0,0,9,0,5,1,2,0,8,1,9,1,9,7,0,9,9,0,0,9,0,5,1,2,0,8,1,9,1,9,7,0,9,9]; const big = BigInt(a.reverse().join("")); 

Thus your function would be

 const addTwoNumbers = (a, b) => ( BigInt(a.reverse().join("")) + BigInt(b.reverse().join("")) ).toString().split("").reverse(); 

But that takes the puz out of puzzle me thinks.

Carry

The aim is to carry the remainder of each addition onto the next digit. This is fundamental to all ALU (Arithmetic Logic Units) that are part of almost every modern CPU. (In the case of binary the carry is 1 or 0)

So when you add two values 9 + 9 the result is 8 and carry 1. You then add the 1 to the next digit. If no digit add it to zero. The result is 18.

The function is thus

Example A

function addNumbers(a, b) { const sum = []; var i = 0, carry = 0; while (i < a.length || i < b.length || carry > 0) { carry += (a[i] ? a[i] : 0) + (b[i] ? b[i] : 0); sum.push(carry % 10); carry = carry / 10 | 0; i++; } return sum; } 

Note That it continues adding digits until the carry is zero.

Performance

I am not surprised that the big int solution is nearly 7 times slower than carry method (example A) above, but this is due to the reverses, joins, and split

Big int are not fast (Very slow compared to standard JS numbers), doing the same sum on big int literals is only 5 times faster than the carry method (example A)

NOTES

BigInt is very new and you should check the browser for support before using it.

Big int also sees the arrival of 64bit int arrays (YAY YAY YAY) BigUint64Array, BigInt64Array (sorry MDN has empty pages on these references)

Answer 2

From a short review

• I prefer to read short words or acronyms, so len ->length ideally
• Consider Math.max() to determine the lengthiest array
• From the challenge, it seems there is no need to sanitize anything
• addTwoNumbers <- this name should give a hint that perhaps the approach is wrong

This is my counter proposal:

const a1 = [2,4,3]; const a2 = [5,6,4]; function addTwoNumbers(nl1, nl2) { function toNumber(digitList){ return digitList.reverse().join('') * 1; } return (toNumber(nl1) + toNumber(nl2) + '').split('').reverse(); } console.log(addTwoNumbers(a1, a2));