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.
Comments
Post a Comment