43. Multiply Strings

Multiply Strings

Problem Description

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

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

 

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

 

Constraints:

• 1 <= num1.length, num2.length <= 200
• num1 and num2 consist of digits only.
• Both num1 and num2 do not contain any leading zero, except the number 0 itself.

Approach) Brute Force

var multiply = function (num1, num2) {
    let z = [];
    let hold = 0;
    let totalLength = num1.length + num2.length;

    if (num1 === '0' || num2 === '0') {
        return '0';
    }

    if (num1 === '1' || num2 === '1') {
        return num1 === '1'
            ? num2
            : num1;
    }

    num1 = num1.split('').reverse();
    num2 = num2.split('').reverse();

    for (let k = 0; k < totalLength; k++) {
        for (let i = 0; i < num1.length; i++) {
            let j = k - i;

            if (num2[j]) {
                hold = hold + (num1[i] * num2[j]);
            }

        }

        if(k === totalLength -1 && hold === 0){
            continue;
        }

        z[k] = hold % 10;
        hold = Math.trunc(hold / 10);
    }

    return z.reverse().join('');
};

Approach) Another Brute Force

• The length of both num1 and num2 is < 110.
• Both num1 and num2 contain only digits 0-9.
• Both num1 and num2 do not contain any leading zero, except the number 0 itself.
• You must not use any built-in BigInteger library or convert the inputs to integers directly.

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var multiply = function(num1, num2) {
  var len1 = num1.length;
  var len2 = num2.length;
  var res = Array(len1 + len2).fill(0);
  var carry = 0;
  var val = 0;
  var index = 0;

  for (var i = len1 - 1; i >= 0; i--) {
    carry = 0;
    for (var j = len2 - 1; j >= 0; j--) {
      index = len1 + len2 - 2 - i - j;
      val= (num1[i] * num2[j]) + carry + res[index];
      carry = Math.floor(val / 10);
      res[index] = val % 10;
    }
    if (carry) res[index + 1] = carry;
  }

  while (res.length > 1 && res[res.length - 1] === 0) res.pop();

  return res.reverse().join('');
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem 43. Multiply Strings

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!