Given two numeric strings A and B, the task is to find the product of the two numeric strings efficiently.
Example:
Input: A = 5678, B = 1234
Output: 7006652Input: A = 74638463789, B = 35284567382
Output: 2633585904851937530398
Approach: The given problem can be solved using Karastuba’s Algorithm for Fast Multiplication, the idea is to append zeroes in front of the integers such that both the integers have an equal and even number of digits n. Thereafter, divide the numbers in the following way:
A = Al * 10n/2 + Ar [Al and Ar contain leftmost and rightmost n/2 digits of A]
B = Bl * 10n/2 + Br [Bl and Br contain leftmost and rightmost n/2 digits of B]
- Therefore, the product A * B can also be represented as follows:
A * B = (Al * 10n/2 + Ar) * (Bl * 10n/2 + Br)
=> A * B = 10n*Al*Bl + 10n/2*(Al*Br + Bl*Ar) + Ar*Br
=> A * B = 10n*Al*Bl + 10n/2*((Al + Ar)*(Bl + Br) – Al*Bl – Ar*Br) + Ar*Br [since Al*Br + Bl*Ar = (Al + Ar)*(Bl + Br) – Al*Bl – Ar*Br]
Notice that the above expression only requires three multiplications Al*Bl, Ar*Br, and (Al + Ar)*(Bl + Br), instead of the standard four. Hence, the recurrence becomes T(n) = 3T(n/2) + O(n) and solution of this recurrence is O(n1.59). This idea has been discussed more thoroughly in this article. Therefore the above problem can be solved using the steps below:
- Create a function findSum(), which finds the sum of two large numbers represented as strings. Similarly, create a function findDiff(), which finds the difference of two large numbers represented as strings.
- In the recursive function multiply(A, B), which multiplies the numbers using Karatsuba’s Algorithm, firstly append zeroes in front of A and B to make their digit count equal and even.
- Then calculate the values of Al, Ar, Bl, and Br as defined above and recursively find the values of multiply(Al, Bl), multiply(Ar, Br), and multiply((Al + Ar), (Bl + Br)) and plug their values in the above-derived equation.
- Print the answer to the equation after removing the leading zeroes from it.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the sum of larger// numbers represented as a stringstring findSum(string str1, string str2){ // Before proceeding further, make // sure length of str2 is larger if (str1.length() > str2.length()) swap(str1, str2); // Stores the result string str = ""; // Calculate length of both string int n1 = str1.length(); int n2 = str2.length(); // Reverse both of strings reverse(str1.begin(), str1.end()); reverse(str2.begin(), str2.end()); int carry = 0; for (int i = 0; i < n1; i++) { // Find the sum of the current // digits and carry int sum = ((str1[i] - '0') + (str2[i] - '0') + carry); str.push_back(sum % 10 + '0'); // Calculate carry for next step carry = sum / 10; } // Add remaining digits of larger number for (int i = n1; i < n2; i++) { int sum = ((str2[i] - '0') + carry); str.push_back(sum % 10 + '0'); carry = sum / 10; } // Add remaining carry if (carry) str.push_back(carry + '0'); // Reverse resultant string reverse(str.begin(), str.end()); return str;}// Function to find difference of larger// numbers represented as stringsstring findDiff(string str1, string str2){ // Stores the result of difference string str = ""; // Calculate length of both string int n1 = str1.length(), n2 = str2.length(); // Reverse both of strings reverse(str1.begin(), str1.end()); reverse(str2.begin(), str2.end()); int carry = 0; // Run loop till small string length // and subtract digit of str1 to str2 for (int i = 0; i < n2; i++) { // Compute difference of the // current digits int sub = ((str1[i] - '0') - (str2[i] - '0') - carry); // If subtraction < 0 then add 10 // into sub and take carry as 1 if (sub < 0) { sub = sub + 10; carry = 1; } else carry = 0; str.push_back(sub + '0'); } // Subtract the remaining digits of // larger number for (int i = n2; i < n1; i++) { int sub = ((str1[i] - '0') - carry); // If the sub value is -ve, // then make it positive if (sub < 0) { sub = sub + 10; carry = 1; } else carry = 0; str.push_back(sub + '0'); } // Reverse resultant string reverse(str.begin(), str.end()); // Return answer return str;}// Function to remove all leading 0s// from a given stringstring removeLeadingZeros(string str){ // Regex to remove leading 0s // from a string const regex pattern("^0+(?!$)"); // Replaces the matched value // with given string str = regex_replace(str, pattern, ""); return str;}// Function to multiply two numbers// using Karatsuba algorithmstring multiply(string A, string B){ if (A.length() > B.length()) swap(A, B); // Make both numbers to have // same digits int n1 = A.length(), n2 = B.length(); while (n2 > n1) { A = "0" + A; n1++; } // Base case if (n1 == 1) { // If the length of strings is 1, // then return their product int ans = stoi(A) * stoi(B); return to_string(ans); } // Add zeros in the beginning of // the strings when length is odd if (n1 % 2 == 1) { n1++; A = "0" + A; B = "0" + B; } string Al, Ar, Bl, Br; // Find the values of Al, Ar, // Bl, and Br. for (int i = 0; i < n1 / 2; ++i) { Al += A[i]; Bl += B[i]; Ar += A[n1 / 2 + i]; Br += B[n1 / 2 + i]; } // Recursively call the function // to compute smaller product // Stores the value of Al * Bl string p = multiply(Al, Bl); // Stores the value of Ar * Br string q = multiply(Ar, Br); // Stores value of ((Al + Ar)*(Bl + Br) // - Al*Bl - Ar*Br) string r = findDiff( multiply(findSum(Al, Ar), findSum(Bl, Br)), findSum(p, q)); // Multiply p by 10^n for (int i = 0; i < n1; ++i) p = p + "0"; // Multiply s by 10^(n/2) for (int i = 0; i < n1 / 2; ++i) r = r + "0"; // Calculate final answer p + r + s string ans = findSum(p, findSum(q, r)); // Remove leading zeroes from ans ans = removeLeadingZeros(ans); // Return Answer return ans;}// Driver Codeint main(){ string A = "74638463789"; string B = "35284567382"; cout << multiply(A, B); return 0;} |
Java
// Java code for the above approach import java.io.*;import java.util.*;class GFG { // Function to find the sum of larger // numbers represented as a string public static String findSum(String str1, String str2) { // Before proceeding further, make sure length of str2 is larger if (str1.length() > str2.length()) { String temp = str1; str1 = str2; str2 = temp; } // Stores the result String str = ""; // Calculate length of both string int n1 = str1.length(); int n2 = str2.length(); // Reverse both of strings str1 = new StringBuilder(str1).reverse().toString(); str2 = new StringBuilder(str2).reverse().toString(); int carry = 0; for (int i = 0; i < n1; i++) { // Find the sum of the current digits and carry int sum = ((str1.charAt(i) - '0') + (str2.charAt(i) - '0') + carry); str += (char)(sum % 10 + '0'); // Calculate carry for next step carry = sum / 10; } // Add remaining digits of larger number for (int i = n1; i < n2; i++) { int sum = ((str2.charAt(i) - '0') + carry); str += (char)(sum % 10 + '0'); carry = sum / 10; } // Add remaining carry if (carry != 0) str += (char)(carry + '0'); // Reverse resultant string str = new StringBuilder(str).reverse().toString(); return str; } // Function to find difference of larger // numbers represented as strings static String findDiff(String str1, String str2) { // Stores the result of difference String str = ""; // Calculate length of both string int n1 = str1.length(), n2 = str2.length(); // Reverse both of strings StringBuilder sb1 = new StringBuilder(str1); StringBuilder sb2 = new StringBuilder(str2); sb1 = sb1.reverse(); sb2 = sb2.reverse(); str1 = sb1.toString(); str2 = sb2.toString(); int carry = 0; // Run loop till small string length // and subtract digit of str1 to str2 for (int i = 0; i < n2; i++) { // Compute difference of the // current digits int sub = ((str1.charAt(i) - '0') - (str2.charAt(i) - '0') - carry); // If subtraction < 0 then add 10 // into sub and take carry as 1 if (sub < 0) { sub = sub + 10; carry = 1; } else carry = 0; str += sub; } // Subtract the remaining digits of // larger number for (int i = n2; i < n1; i++) { int sub = ((str1.charAt(i) - '0') - carry); // If the sub value is -ve, // then make it positive if (sub < 0) { sub = sub + 10; carry = 1; } else carry = 0; str += sub; } // Reverse resultant string str = new StringBuilder(str).reverse().toString(); // Return answer return str; } // Function to remove all leading 0s // from a given string public static String removeLeadingZeros(String str) { // Regex to remove leading 0s from a string String pattern = "^0+(?!$)"; // Replaces the matched value with given string str = str.replaceAll(pattern, ""); return str; } // Function to multiply two numbers // using Karatsuba algorithm public static String multiply(String A, String B) { if (A.length() > B.length()) { String temp = A; A = B; B = temp; } // Make both numbers to have // same digits int n1 = A.length(), n2 = B.length(); while (n2 > n1) { A = "0" + A; n1++; } // Base case if (n1 == 1) { // If the length of strings is 1, // then return their product int ans = Integer.parseInt(A) * Integer.parseInt(B); return Integer.toString(ans); } // Add zeros in the beginning of // the strings when length is odd if (n1 % 2 == 1) { n1++; A = "0" + A; B = "0" + B; } String Al = "", Ar = "", Bl = "", Br = ""; // Find the values of Al, Ar, // Bl, and Br. for (int i = 0; i < n1 / 2; ++i) { Al += A.charAt(i); Bl += B.charAt(i); Ar += A.charAt(n1 / 2 + i); Br += B.charAt(n1 / 2 + i); } // Recursively call the function // to compute smaller product // Stores the value of Al * Bl String p = multiply(Al, Bl); // Stores the value of Ar * Br String q = multiply(Ar, Br); // Stores value of ((Al + Ar)*(Bl + Br) // - Al*Bl - Ar*Br) String r = findDiff( multiply(findSum(Al, Ar), findSum(Bl, Br)), findSum(p, q)); // Multiply p by 10^n for (int i = 0; i < n1; ++i) p = p + "0"; // Multiply s by 10^(n/2) for (int i = 0; i < n1 / 2; ++i) r = r + "0"; // Calculate final answer p + r + s String ans = findSum(p, findSum(q, r)); // Remove leading zeroes from ans ans = removeLeadingZeros(ans); // Return Answer return ans; } public static void main(String[] args) { String A = "74638463789"; String B = "35284567382"; System.out.println(multiply(A, B)); } } |
C#
using System;using System.Linq;using System.Text;class GFG { // Function to find the sum of larger // numbers represented as a string public static string FindSum(string str1, string str2) { // Before proceeding further, make sure length of // str2 is larger if (str1.Length > str2.Length) { string temp = str1; str1 = str2; str2 = temp; } // Stores the result string str = ""; // Calculate length of both string int n1 = str1.Length; int n2 = str2.Length; // Reverse both of strings str1 = new string(str1.Reverse().ToArray()); str2 = new string(str2.Reverse().ToArray()); int carry = 0; for (int i = 0; i < n1; i++) { // Find the sum of the current digits and carry int sum = ((str1[i] - '0') + (str2[i] - '0') + carry); str += (char)(sum % 10 + '0'); // Calculate carry for next step carry = sum / 10; } // Add remaining digits of larger number for (int i = n1; i < n2; i++) { int sum = ((str2[i] - '0') + carry); str += (char)(sum % 10 + '0'); carry = sum / 10; } // Add remaining carry if (carry != 0) str += (char)(carry + '0'); // Reverse resultant string return new string(str.Reverse().ToArray()); } // Function to find difference of larger // numbers represented as strings static string FindDiff(string str1, string str2) { // Stores the result of difference string str = ""; // Calculate length of both string int n1 = str1.Length, n2 = str2.Length; // Reverse both of strings str1 = new string(str1.Reverse().ToArray()); str2 = new string(str2.Reverse().ToArray()); int carry = 0; // Run loop till small string length // and subtract digit of str1 to str2 for (int i = 0; i < n2; i++) { // Compute difference of the // current digits int sub = ((str1[i] - '0') - (str2[i] - '0') - carry); // If subtraction < 0 then add 10 // into sub and take carry as 1 if (sub < 0) { sub = sub + 10; carry = 1; } else carry = 0; str += sub; } // Subtract the remaining digits of // larger number for (int i = n2; i < n1; i++) { int sub = ((str1[i] - '0') - carry); // If the sub value is -ve, // then make it positive if (sub < 0) { sub = sub + 10; carry = 1; } else carry = 0; str += sub; } return new string(str.Reverse().ToArray()); } // Function to remove all leading 0s // from a given string public static string RemoveLeadingZeros(string input) { int i = 0; while (i < input.Length && input[i] == '0') { i++; } return i == input.Length ? "0" : input.Substring(i); } // Function to multiply two numbers // using Karatsuba algorithm public static string Multiply(string A, string B) { if (A.Length > B.Length) { string temp = A; A = B; B = temp; } // Make both numbers to have // same digits int n1 = A.Length, n2 = B.Length; while (n2 > n1) { A = "0" + A; n1++; } // Base case if (n1 == 1) { // If the length of strings is 1, // then return their product return Convert.ToString(Convert.ToInt32(A) * Convert.ToInt32(B)); } // Add zeros in the beginning of // the strings when length is odd if (n1 % 2 == 1) { n1++; A = "0" + A; B = "0" + B; } string Al = "", Ar = "", Bl = "", Br = ""; // Find the values of Al, Ar, // Bl, and Br. for (int i = 0; i < n1 / 2; ++i) { Al += A[i]; Bl += B[i]; Ar += A[n1 / 2 + i]; Br += B[n1 / 2 + i]; } // Recursively call the function // to compute smaller product // Stores the value of Al * Bl string p = Multiply(Al, Bl); // Stores the value of Ar * Br string q = Multiply(Ar, Br); // Stores value of ((Al + Ar)*(Bl + Br) // - Al*Bl - Ar*Br) string r = FindDiff( Multiply(FindSum(Al, Ar), FindSum(Bl, Br)), FindSum(p, q)); // Multiply p by 10^n for (int i = 0; i < n1; ++i) p = p + "0"; // Multiply s by 10^(n/2) for (int i = 0; i < n1 / 2; ++i) r = r + "0"; // Calculate final answer p + r + s string ans = FindSum(p, FindSum(q, r)); // Remove leading zeroes from ans ans = RemoveLeadingZeros(ans); // Return Answer return ans; } public static void Main(string[] args) { string A = "74638463789"; string B = "35284567382"; Console.WriteLine(Multiply(A, B)); }} |
Output:
2633585904851937530398
Time Complexity: O(Nlog 3) or O(N1.59), where N is the maximum among the lengths given strings A and B.
Auxiliary Space: O(N2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
