Add Two Number leetcode algo

Question

I was doing following leetCode Problem: https://leetcode.com/problems/add-two-numbers/

And I am not sure why one of my test case is failing

So the question is

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

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

For which I have written following algo

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
const makeLinkedList = (inArr, i) => {
    if (i < 0) return null
    return { val:inArr[i], next:makeLinkedList(inArr, i-1)}
}


var addTwoNumbers = function(l1, l2) {
    let sum = 0
    let i = 1
    while(l1 || l2) {
        if (l1 && l2) {
            sum = sum + l1.val*i + l2.val*i
             l1 = l1.next
             l2 = l2.next
        } else {

        if (l1) {  
            sum = l1.val*i + sum
            l1 = l1.next
        }
        if (l2) {
            sum = l2.val*i + sum
            l2 = l2.next
        }    
      }
        i = i*10
    }
    const sumToString = sum.toLocaleString('fullwide', {useGrouping:false}); 
    return  makeLinkedList(sumToString, sumToString.length-1)
};

The reason in the above code I have used while loop instead of recursively calling functions is mainly to make it more optimized.

anyway, For the following input, my test case is failing

[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]
[5,6,4]

i.e my output is coming to be [0,3,NaN,NaN,1] instead of [6,6,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]

As a note, leetCode compiler will convert array to linkedlist on input. Can someone help me in figuring out why my input might be failing?

You cannot reassemble numbers, parse them with parseInt and split it back, because JS does not have arbitrary precision integer type hence even if your code was "correct" it would have failed on numbers larger than ~2^53. The idea is that you need to add every place and produce result on the go as you iterate those lists — zerkms
– zerkms, Commented Nov 13, 2019 at 23:33

tevemadar · Accepted Answer · 2019-11-14 10:29:52Z

When JavaScript stringifies a number in scientific notation, there will be a + sign for positive exponents. That sequence you see is 1E+30, the NaNs are standing for + and E (because of the reverted order). In fact you could have put a console.log(sum) or console.log(sumToString) and catch the issue without knowing this, just simply seeing what is there.

Not all languages tell you the maximum value they can store without loss in precision, but JavaScript in particular does, Number.MAX_SAFE_INTEGER contains the value 9 007 199 254 740 991 so it is a bit more than 9E+15, far less than 1 + 1E+30 (the longer number).

What you are expected to do is to add the numbers like you have learned in elementary school: add two digits, write one digit, and see if there is an 1 to carry to the next digit-pair you are going to add.

Iterative version:

function makeLinkedList(arr,i){
  i=i || 0;
  return i<arr.length?{val:arr[i], next:makeLinkedList(arr,i+1)}:null;
}

var addTwoNumbers = function(l1, l2) {
  var snt={next:null};
  var cur=snt;
  var carry=0;
  while(l1 || l2 || carry){
    cur.next={next:null};
    cur=cur.next;
    var sum=(l1?l1.val:0)+(l2?l2.val:0)+carry;
    if(sum<10){
      cur.val=sum;
      carry=0;
    } else {
      cur.val=sum-10;
      carry=1;
    }
    l1=l1?l1.next:null;
    l2=l2?l2.next:null;
  }
  return snt.next;
}

var a=[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1];
var b=[5,6,4];
console.log(addTwoNumbers(makeLinkedList(a),makeLinkedList(b)));
a=[9,9];
b=[1,9];
console.log(addTwoNumbers(makeLinkedList(a),makeLinkedList(b)));

Recursive version:

function makeLinkedList(arr,i){
  i=i || 0;
  return i<arr.length?{val:arr[i], next:makeLinkedList(arr,i+1)}:null;
}

var addTwoNumbers = function(l1, l2, carry) {
  if(!(l1 || l2 || carry))
    return null;
  carry=carry || 0;
  var sum=(l1?l1.val:0)+(l2?l2.val:0)+carry;
  return {
    val: sum % 10,
    next: addTwoNumbers(l1?l1.next:null,l2?l2.next:null,sum>9?1:0)
  };
}

var a=[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1];
var b=[5,6,4];
console.log(addTwoNumbers(makeLinkedList(a),makeLinkedList(b)));
a=[9,9];
b=[1,9];
console.log(addTwoNumbers(makeLinkedList(a),makeLinkedList(b)));

Ashita.gupta · Accepted Answer · 2021-11-23 11:41:15Z

Solution for the problem in JavaScript.

var addTwoNumbers = function (l1, l2) {
 let reminder = 0;
 let l1Node = l1;
 let l2Node = l2;

 let list = new ListNode(0);
 let currentNode = list;

 while (l1Node || l2Node) {
    const valueL1 = l1Node ? l1Node.val : 0;
    const valueL2 = l2Node ? l2Node.val : 0;
    let sum = valueL1 + valueL2 + reminder;
    reminder = 0;
    if (sum > 9) {
        reminder = Math.floor(sum / 10);
        sum = sum % 10;

    }

    currentNode.next = new ListNode(sum);
    currentNode = currentNode.next;

    l1Node = l1Node ? l1Node.next : null;
    l2Node = l2Node ? l2Node.next : null;
 }

if (reminder != 0) {
    currentNode.next = new ListNode(reminder);
    currentNode = currentNode.next;
}


return list.next;

};

function ListNode(val, next) {
  this.val = (val === undefined ? 0 : val)
  this.next = (next === undefined ? null : next)
}

const l1 = new ListNode(2, new ListNode(4, new ListNode(3)));
const l2 = new ListNode(5, new ListNode(6))
const res = addTwoNumbers(l1, l2);

console.log(res);

Collectives™ on Stack Overflow

Add Two Number leetcode algo

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related