javascript - Multiply strings - Stack Overflow

admin管理员组

文章数量:1327685

Problem Set- Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

My algorithm seems to work fine for all but one test case of palindrome from 1-9

UPDATE

Javascript has a parse method but I don't want to use that as the problem is from leetcode or a matter of fact from any such site and the problem sets says that explicitly.

//**Input:**
var n1 = "123456789"
var n2 = "987654321"

var multiply = function(str1, str2) {
  var sum = 0, k = 1;
  for( var i = str1.length - 1; i>=0; i--){
      var val1 = parseInt(str1[i], 10) * k;

      k *= 10;
      var d = 1;
      for(var j = str2.length - 1; j >=0; j--){
          var val2 = parseInt(str2[j], 10) * d;
          d *= 10;

          sum +=  val1 * val2;

      }
  }
  return sum.toString();
};

console.log(multiply(n1,n2))

Problem Set- Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

My algorithm seems to work fine for all but one test case of palindrome from 1-9

UPDATE

Javascript has a parse method but I don't want to use that as the problem is from leetcode or a matter of fact from any such site and the problem sets says that explicitly.

//**Input:**
var n1 = "123456789"
var n2 = "987654321"

var multiply = function(str1, str2) {
  var sum = 0, k = 1;
  for( var i = str1.length - 1; i>=0; i--){
      var val1 = parseInt(str1[i], 10) * k;

      k *= 10;
      var d = 1;
      for(var j = str2.length - 1; j >=0; j--){
          var val2 = parseInt(str2[j], 10) * d;
          d *= 10;

          sum +=  val1 * val2;

      }
  }
  return sum.toString();
};

console.log(multiply(n1,n2))

I cannot understand what's going wrong. Other palindromes work fine though.

• javascript
• algorithm
• multiplication

Share Follow edited Jul 19, 2018 at 14:03 HalfWebDev asked Jul 19, 2018 at 13:53 HalfWebDevHalfWebDev 7,6681313 gold badges7171 silver badges110110 bronze badges 15

• 7 What is the code supposed to do? – Pointy Commented Jul 19, 2018 at 13:55
• I have updated a detailed problem statement than only the subject line stating the problem – HalfWebDev Commented Jul 19, 2018 at 13:57
• 1 If you are trying to multiply two strings, then your code meets integer overflow issue. You shouldn't pute the result product in an integer, just use a string as a container to hold your final product. – itsjc Commented Jul 19, 2018 at 13:58
• @cricket_007 I have given the input test case for which it fails i.e. palindrome multiplication – HalfWebDev Commented Jul 19, 2018 at 13:58
• 1 Why aren't you just parsing both numbers, then multiplying? What's the purpose of iterating the digits? Also, have you considered integer overflow? – OneCricketeer Commented Jul 19, 2018 at 13:59

 |  Show 10 more ments

2 Answers 2

Sorted by: Reset to default 6

The purpose of such an exercise is probably that you implement your own multiplication algorithm for big numbers. When an integer (the product in this case) needs more than 15-16 digits, JavaScript number type cannot store that with enough precision, and so the oute will be wrong if you just use the multiplication operator on the inputs.

Even if you sum up smaller products in a number variable, that sum will eventually cross the limit of Number.MAX_SAFE_INTEGER. You need to store the result of smaller calculations in another data structure, like an array or a string.

Here is a simple implementation of the long multiplication algorithm:

function multiply(a, b) {
    const product = Array(a.length+b.length).fill(0);
    for (let i = a.length; i--; null) {
        let carry = 0;
        for (let j = b.length; j--; null) {
            product[1+i+j] += carry + a[i]*b[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");
}

console.log(multiply("123456789", "987654321"));

Since ECMAScript 2020, JavaScript has the bigint data type, with which you can do such multiplications out of the box (note the n suffix):

console.log((123456789n * 987654321n).toString());

NB: In a browser you don't need to call toString() explicitly, but the above Stack Snippet console implementation is limited, so it needs it.

With Chrome you have access to BigInt arithmetic with arbitrarily (usual disclaimers apply) large integers. Run the example to see that it does make a difference.

let p1 = BigInt(1000000000) * BigInt(123456789) + BigInt(123456789)
  , p2 = BigInt(1000000000) * BigInt(987654321) + BigInt(987654321)
  ;
  
console.log(`standard: =${123456789 * 987654321}`);
console.log(`standard large: =${123456789123456789 * 987654321987654321}`);
console.log(`BigInt: =${p1 * p2}`);

本文标签： javascriptMultiply stringsStack Overflow