Multiply Strings - CPP Solution

1. Introduction

This blog post explores how to multiply two large numbers represented as strings in C++. This problem is a practical example of how to handle arithmetic operations on numbers larger than those that can be stored in primitive data types.

Problem

Given two non-negative integers num1 and num2 represented as strings, the task is to return the product of num1 and num2, also represented as a string. The challenge lies in correctly multiplying these large numbers without using built-in big integer libraries.

2. Solution Steps

1. Initialize a string to store the result, with a length equal to the sum of lengths of num1 and num2.

2. Use two nested loops to multiply each digit of num1 with each digit of num2 and store the result in the corresponding position in the result string.

3. Handle carry-over for each multiplication.

4. After completing the multiplication, process the result string to remove any leading zeros.

5. Return the final result string.

3. Code Program

#include <iostream>
#include <string>
using namespace std;

// Function to multiply two numbers represented as strings
string multiply(string num1, string num2) {
    int n1 = num1.size(), n2 = num2.size();
    string result(n1 + n2, '0'); // Initialize result string

    for (int i = n1 - 1; i >= 0; i--) {
        for (int j = n2 - 1; j >= 0; j--) {
            int product = (num1[i] - '0') * (num2[j] - '0') + (result[i + j + 1] - '0');
            result[i + j + 1] = product % 10 + '0'; // Store last digit
            result[i + j] += product / 10; // Add carry-over
        }
    }

    // Remove leading zeros
    size_t start = result.find_first_not_of("0");
    if (start != string::npos) {
        return result.substr(start);
    } else {
        return "0";
    }
}

int main() {
    string num1 = "123", num2 = "456";
    cout << "Product: " << multiply(num1, num2) << endl;
    return 0;
}

Output:

Product: 56088

Explanation:

1. The input strings "123" and "456" are multiplied as if they were large numbers.

2. The multiplication is performed digit by digit, from right to left, and the partial results are added.

3. Carry-overs for each multiplication are correctly handled and added to the next position.

4. The result is a string "56088", which is the product of "123" and "456".

5. The function avoids integer overflow issues and accurately calculates the product of large numbers represented as strings.