Leetcode Algorithm for Adding Two Numbers

Question

Leetcode Algorithm for Adding Two Numbers

Recently, I attempted the following leetCode Problem:

However, I encountered an issue where one of my test cases failed and I'm unsure why.

Here is the scenario:

You are provided with two non-empty linked lists that represent two non-negative integers. The digits are stored in reverse order, with each node containing a single digit. Your task is to add the two numbers and return the result as a linked list.

You can assume that the numbers do not contain any leading zeros, except for the number 0 itself.

To tackle this problem, I devised the following algorithm:

/**
 * 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 behind using a while loop instead of recursive functions in the code above was mainly for optimization purposes.

However, I faced a challenge as my test case failed for the input below:

[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]

My output returned as [0,3,NaN,NaN,1], rather than

[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]

.

If anyone could assist me in identifying why my input might be failing, it would be greatly appreciated.

javascript

Answer 1

Answer №1

When JavaScript converts a number into scientific notation, it will include a "+" sign for positive exponents. The output you are seeing is "1E+30", with the "NaN"s representing the symbols "+" and "E" (in reverse order). Simply by using a console log of either "sum" or "sumToString", you could have easily identified this issue without prior knowledge.

Not all programming languages disclose their maximum precision values, but JavaScript does through Number.MAX_SAFE_INTEGER, which holds the value "9 007 199 254 740 991". This is slightly more than "9E+15", but significantly less than "1 + 1E+30" (the longer number).

The correct approach is to add the numbers as taught in elementary school – adding two digits, writing one digit, and carrying over if there is a remainder to the next set of digits to be added.

Iterative method:

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

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

var numA = [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 numB = [5, 6, 4];
console.log(addTwoNumbers(createLinkedList(numA), createLinkedList(numB)));

numA = [9, 9];
numB = [1, 9];
console.log(addTwoNumbers(createLinkedList(numA), createLinkedList(numB)));

Recursive method:

function createLinkedList(arr, index) {
  index = index || 0;
  return index < arr.length ? { val: arr[index], next: createLinkedList(arr, index + 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)
  };
}

numA = [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];
numB = [5, 6, 4];
console.log(addTwoNumbers(createLinkedList(numA), createLinkedList(numB)));

numA = [9, 9];
numB = [1, 9];
console.log(addTwoNumbers(createLinkedList(numA), createLinkedList(numB)));

Answer 2

When JavaScript converts a number into scientific notation, it will include a "+" sign for positive exponents. The output you are seeing is "1E+30", with the "NaN"s representing the symbols "+" and "E" (in reverse order). Simply by using a console log of either "sum" or "sumToString", you could have easily identified this issue without prior knowledge.

Not all programming languages disclose their maximum precision values, but JavaScript does through Number.MAX_SAFE_INTEGER, which holds the value "9 007 199 254 740 991". This is slightly more than "9E+15", but significantly less than "1 + 1E+30" (the longer number).

The correct approach is to add the numbers as taught in elementary school – adding two digits, writing one digit, and carrying over if there is a remainder to the next set of digits to be added.

Iterative method:

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

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

var numA = [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 numB = [5, 6, 4];
console.log(addTwoNumbers(createLinkedList(numA), createLinkedList(numB)));

numA = [9, 9];
numB = [1, 9];
console.log(addTwoNumbers(createLinkedList(numA), createLinkedList(numB)));

Recursive method:

function createLinkedList(arr, index) {
  index = index || 0;
  return index < arr.length ? { val: arr[index], next: createLinkedList(arr, index + 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)
  };
}

numA = [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];
numB = [5, 6, 4];
console.log(addTwoNumbers(createLinkedList(numA), createLinkedList(numB)));

numA = [9, 9];
numB = [1, 9];
console.log(addTwoNumbers(createLinkedList(numA), createLinkedList(numB)));

Answer 3

Answer №2

JavaScript solution to address a specific issue.

var addNumbers = function (num1, num2) {
 let remainder = 0;
 let number1Node = num1;
 let number2Node = num2;

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

 while (number1Node || number2Node) {
    const valueNum1 = number1Node ? number1Node.val : 0;
    const valueNum2 = number2Node ? number2Node.val : 0;
    let sum = valueNum1 + valueNum2 + remainder;
    remainder = 0;
    if (sum > 9) {
        remainder = Math.floor(sum / 10);
        sum = sum % 10;

    }

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

    number1Node = number1Node ? number1Node.next : null;
    number2Node = number2Node ? number2Node.next : null;
 }

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


return list.next;

};

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

const num1 = new ListNode(2, new ListNode(4, new ListNode(3)));
const num2 = new ListNode(5, new ListNode(6))
const result = addNumbers(num1, num2);

console.log(result);

Answer 4

JavaScript solution to address a specific issue.

var addNumbers = function (num1, num2) {
 let remainder = 0;
 let number1Node = num1;
 let number2Node = num2;

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

 while (number1Node || number2Node) {
    const valueNum1 = number1Node ? number1Node.val : 0;
    const valueNum2 = number2Node ? number2Node.val : 0;
    let sum = valueNum1 + valueNum2 + remainder;
    remainder = 0;
    if (sum > 9) {
        remainder = Math.floor(sum / 10);
        sum = sum % 10;

    }

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

    number1Node = number1Node ? number1Node.next : null;
    number2Node = number2Node ? number2Node.next : null;
 }

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


return list.next;

};

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

const num1 = new ListNode(2, new ListNode(4, new ListNode(3)));
const num2 = new ListNode(5, new ListNode(6))
const result = addNumbers(num1, num2);

console.log(result);

Leetcode Algorithm for Adding Two Numbers

Answer №1

Answer №2

Similar questions

Issue with ng-true-value in AngularJS version 1.6.1 - not functioning as expected

Get the package from a Lerna-managed monorepository using a git URL

Syntax for private members in ES6 classes

checkbox appear based on vue condition

The text loader feature in THREE.js is failing to load

Guide on producing a milky overlay using Vue js

What is the best way to toggle an element's visibility using the select tag?

The process of obtaining and sending a token from an HTML page while submitting a form request to a Laravel 5 application involves a few key steps

Deactivate a <tr> element if any of its <td> cells contain a value

Ways to swap out element within ViewContainerRef in Angular

Converting large JSON data (approximately 100MB) into an Excel file using JavaScript

What is causing the check box in the simple_form view to consistently return a value of 1 when checked or unchecked in rails 3.2?

Returning a PHP variable to AJAX communication

Javascript's asynchronous initiator

Tips for utilizing ajax function to refresh database entries

Set up a trigger to activate when a WordPress User Role is selected, or alternatively, execute JavaScript

What could be causing this code to malfunction on a mobile device?

Ever since updating my Node JS, the functionality of the MaterializeCSS carousel methods has ceased to work

Determine the total of the final column in recently added rows by utilizing JavaScript

Building an HTTP request and response directly from an active socket in a Node.js environment