Multiply Strings

Problem Statement

The task involves multiplying two numbers, given in string format, without directly converting them into integers or using large integer libraries. You will need to simulate the multiplication process that you would typically do by hand or using basic arithmetic algorithms because the strings can be up to 200 characters long. This process must return the product also as a string, ensuring compatibility with very large numbers that exceed typical integer support in most programming languages.

Examples

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 and Intuition

To solve the problem of multiplying two large numbers provided as strings, the classic approach inspired by long multiplication (or grade-school multiplication) is used. This method can be intuitive when visualized as aligning numbers in a staggered format, multiplying digits in a pairwise manner from right to left, and keeping track of carry-over values.

1. Initial Setup:

   • Identify the lengths of the two strings, num1 and num2.
   • Create an array (or list) to hold the intermediate results, with a size that is the sum of the lengths of num1 and num2. This array will store the sums of the products of digit pairs.

2. Multiplying Each Digit:

   • For each digit in num1 and each digit in num2, calculate the product. Since the characters represent digits, they need to be converted to integers for arithmetic operations.
   • Calculate the positions in the results array where the result of the product of two digits should be added.

3. Handling Carry Over:

   • Once all products are added to the result array, handle the carry for each position starting from the least significant position (the end of the array).
   • Adjust each position to ensure it represents a single digit, transferring the excess to the next left position.

4. Building the Final Product String:

   • Convert the result array back to a string. Be mindful of not including initial zeros except where the entire product results in zero.
   • Consider edge cases, such as when one or both of the numbers are zero.

Using this algorithmic approach handles the constraints effectively, ensuring operation within the limits without running into performance or capacity issues typical integer operations might face. This method directly utilizes the positional notation system, which underlies decimal multiplication, adapting it for efficient computation even with extremely large numbers.

Solutions

class Solution {
public:
    string multiplyStrings(string number1, string number2) {
        if (number1 == "0" || number2 == "0") return "0";
    
        reverse(number1.begin(), number1.end());
        reverse(number2.begin(), number2.end());
    
        int len = number1.size() + number2.size();
        string result(len, '0');
    
        for (int idx2 = 0; idx2 < number2.size(); idx2++) {
            int digit2 = number2[idx2] - '0';
            for (int idx1 = 0; idx1 < number1.size(); idx1++) {
                int digit1 = number1[idx1] - '0';
                int carry = result[idx1 + idx2] - '0';
                int product = digit1 * digit2 + carry;
                result[idx1 + idx2] = (product % 10) + '0';
                result[idx1 + idx2 + 1] += (product / 10);
            }
        }
    
        while (result.back() == '0' && result.length() > 1) result.pop_back();
        reverse(result.begin(), result.end());
            
        return result;
    }
};