Multiply Strings - [Leetcode] with JavaScript

Question

I've been tacking this problem far too long and I can't seem to find what is wrong with my logic.

Prompt:

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

The length of both num1 and num2 is < 110.

Both num1 and num2 contains only digits 0-9.

Both num1 and num2 does not contain any leading zero.

You must not use any built-in BigInteger library or convert the inputs to integer directly.

Here is my attempt:

var multiply = function(num1, num2) {
  var result = 0;
  // if any of the nums is 0, automatically it is zero
  if (num1[0] === '0' || num2[0] === '0') {
    return '0'
  };

  var length1 = num1.length - 1;
  var length2 = num2.length - 1;
  var counterI = 0;
  var iBase10 = 1;
  for (var i = length1; i >= 0; i--) {
    iBase10 = Math.pow(10, counterI)
    counterI++;
    var counterJ = 0
    var jBase10 = 1;
    for (var j = length2; j >= 0; j--) {
      jBase10 = Math.pow(10, counterJ)
      counterJ++;
      result += (num1[i] * iBase10) * (num2[j] * jBase10)
    }
  }
  return result.toString()
};

var result = multiply("123456789", "987654321");

console.log(result); // should be 121932631112635269

Essentially the logic is that I can adding result each multiplication I make starting from the right side of the strings to the left (to all possible combination, hence the nested for loop).

As the indexes moves to the left, the base10 is increased to power of 10 so each calculation is set accordingly.

However, I can't seem to find what is wrong when I type in as follows:

var result = multiply("123456789","987654321");

The result I get is 121932631112635260, yet the actual answer is 121932631112635269

I'm so slightly close the answer!

you 'result' variable should be an array, and you need to add logic to handle the carry. — algojava
– algojava, Commented Feb 12, 2017 at 18:31
Even if you fix what is currently giving you the wrong last digit, you have a much more important issue: iBase10, jBase10 and result will become inaccurate numbers once you start playing with inputs that have more than 17 digits. You need a different approach. — trincot
– trincot, Commented Feb 12, 2017 at 18:33
You're code uses basic number type of javascript which cannot hold very big values! Try this and you'll understand what is happening: parseInt("121932631112635269");! — ibrahim mahrir
– ibrahim mahrir, Commented Feb 12, 2017 at 18:34
I think you should handle the sum of big numbers using strings not numbers! — ibrahim mahrir
– ibrahim mahrir, Commented Feb 12, 2017 at 18:35

trincot · Accepted Answer · 2023-02-17 08:22:45Z

Your actual result is inaccurate because you store the result in one single number-typed variable, and also the intermediate variables iBase10 and jBase10 would at a certain point become inaccurate. JavaScript uses 64-bit floats for storing numbers, so for numbers with approximately 17 or more decimal digits this representation loses accuracy. This is why you get a final 0 digit instead of a 9.

Since ECMAScript 2020, there is the BigInt data type, which makes this exercise trivial -- there is no precision loss when you use that:

const multiply = (a, b) => (BigInt(a) * BigInt(b)).toString();

But this code challenge was created when JavaScript had not added BigInt support yet, and we can assume that the intention was to solve the challenge without it. In that case you need to work with numbers that are smaller, and stay within the limits of what JavaScript can manage. The final result should be a string, because as soon as you convert that to number, the inaccuracy will kick in.

Here is a simple implementation, which mimics what you would do on a piece of paper: you calculate the products of each digit of number 1 with each digit of number 2, and sum these products at the right digit-position in the result, carrying over any overflow to the next digit:

    123 
    456
------- *
    738      <--- intermediate products
   615
  492
------- +
  56088     <---- sum of those products

var multiply = function(num1, num2) {
    // Result can have at most this number of digits:
    var result = Array(num1.length + num2.length).fill(0);
    for (var j = num2.length - 1; j >= 0; j--) {
        // k is the index in the result: where to add to 
        var k = num1.length + j;
        var overflow = 0;
        for (var i = num1.length - 1; i >= 0; i--) {
            product = num2[j] * num1[i] + overflow + result[k];
            result[k] = product % 10;
            overflow = (product - result[k]) / 10;
            k--;
        }
        result[k] += overflow;
    }
    // Convert result to string, removing any prepadded zeroes
    return result.join('').replace(/^0+(.)/, '$1');
}

// I/O handling
var inputs = document.querySelectorAll('input');
var output = document.querySelector('span');

inputs[0].oninput = calculate;
inputs[1].oninput = calculate;

function calculate() {
  output.textContent = multiply(inputs[0].value, inputs[1].value);
}

input { width: 40em }

Number 1: <input><br>
Number 2: <input><br>
Product: <span></span>

There are smarter algorithms, like the Karatsuba algorithm, which use less operations to get a correct product.

Kondal · Accepted Answer · 2020-09-30 15:29:53Z

0

var multiply = function(num1, num2) {
let product = new Array(num1.length + num2.length).fill(0)
for (let i = num1.length; i--;) {
    let carry = 0
    for (let j = num2.length; j--;) {
        product[1 + i + j] += carry + num1[i] * num2[j]
        carry = Math.floor(product[1+i+j] / 10);
        product[1 + i + j] = product[1 + i + j] % 10
    }
    product[i] += carry
}
return product.join("").replace(/^0*(\d)/, "$1");
};

OR

var multiply = function(a, b) {
   return (BigInt(a)*BigInt(b)).toString()
};

answered Sep 30, 2020 at 15:29

Kondal

2,9905 gold badges29 silver badges41 bronze badges

Comments

goten · Accepted Answer · 2021-11-17 02:09:29Z

-1

var multiply = function(num1, num2) {
    let num1num = num1.replace('"', '');
    let num2num = num2.replace('"', '');
    let product = BigInt(num1num) * BigInt(num2num);
    let productString = product.toString();
    return productString;
};

answered Nov 17, 2021 at 2:09

goten

11 bronze badge

1 Comment

tdy Over a year ago

Please consider adding a brief explanation of how and why this solves the problem. This will help readers to better understand your solution.

Collectives™ on Stack Overflow

Multiply Strings - [Leetcode] with JavaScript

3 Answers 3

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related