Data Modelling & AI Data Structure & Algorithm

Multiply Large Numbers represented as Strings

31 July 2024

3

Given two positive numbers as strings. The numbers may be very large (may not fit in long long int), the task is to find product of these two numbers.
Examples:

Input : num1 = 4154  
        num2 = 51454
Output : 213739916 

Input :  num1 = 654154154151454545415415454  
         num2 = 63516561563156316545145146514654 
Output : 41549622603955309777243716069997997007620439937711509062916

The idea is based on school mathematics.

We start from last digit of second number multiply it with first number. Then we multiply second digit of second number with first number, and so on. We add all these multiplications. While adding, we put i-th multiplication shifted.
The approach used in below solution is to keep only one array for result. We traverse all digits first and second numbers in a loop and add the result at appropriate position.

C++

// C++ program to multiply two numbers represented
// as strings.
#include<bits/stdc++.h>
using namespace std;
 
// Multiplies str1 and str2, and prints result.
string multiply(string num1, string num2)
{
    int len1 = num1.size();
    int len2 = num2.size();
    if (len1 == 0 || len2 == 0)
    return "0";
 
    // will keep the result number in vector
    // in reverse order
    vector<int> result(len1 + len2, 0);
 
    // Below two indexes are used to find positions
    // in result. 
    int i_n1 = 0; 
    int i_n2 = 0; 
     
    // Go from right to left in num1
    for (int i=len1-1; i>=0; i--)
    {
        int carry = 0;
        int n1 = num1[i] - '0';
 
        // To shift position to left after every
        // multiplication of a digit in num2
        i_n2 = 0; 
         
        // Go from right to left in num2             
        for (int j=len2-1; j>=0; j--)
        {
            // Take current digit of second number
            int n2 = num2[j] - '0';
 
            // Multiply with current digit of first number
            // and add result to previously stored result
            // at current position. 
            int sum = n1*n2 + result[i_n1 + i_n2] + carry;
 
            // Carry for next iteration
            carry = sum/10;
 
            // Store result
            result[i_n1 + i_n2] = sum % 10;
 
            i_n2++;
        }
 
        // store carry in next cell
        if (carry > 0)
            result[i_n1 + i_n2] += carry;
 
        // To shift position to left after every
        // multiplication of a digit in num1.
        i_n1++;
    }
 
    // ignore '0's from the right
    int i = result.size() - 1;
    while (i>=0 && result[i] == 0)
    i--;
 
    // If all were '0's - means either both or
    // one of num1 or num2 were '0'
    if (i == -1)
    return "0";
 
    // generate the result string
    string s = "";
     
    while (i >= 0)
        s += std::to_string(result[i--]);
 
    return s;
}
 
// Driver code
int main()
{
    string str1 = "1235421415454545454545454544";
    string str2 = "1714546546546545454544548544544545";
     
    if((str1.at(0) == '-' || str2.at(0) == '-') && 
        (str1.at(0) != '-' || str2.at(0) != '-' ))
        cout<<"-";
 
 
    if(str1.at(0) == '-')
        str1 = str1.substr(1);
   
    if(str2.at(0) == '-')
        str2 = str2.substr(1);
 
    cout << multiply(str1, str2);
    return 0;
}

Java

// Java program to multiply two numbers 
// represented as Strings.
import java.util.*;
import java.io.*;
class GFG
{
     
// Multiplies str1 and str2, and prints result.
static String multiply(String num1, String num2)
{
    int len1 = num1.length();
    int len2 = num2.length();
    if (len1 == 0 || len2 == 0)
        return "0";
 
    // will keep the result number in vector
    // in reverse order
    int result[] = new int[len1 + len2];
 
    // Below two indexes are used to 
    // find positions in result. 
    int i_n1 = 0; 
    int i_n2 = 0; 
     
    // Go from right to left in num1
    for (int i = len1 - 1; i >= 0; i--)
    {
        int carry = 0;
        int n1 = num1.charAt(i) - '0';
 
        // To shift position to left after every
        // multipliccharAtion of a digit in num2
        i_n2 = 0; 
         
        // Go from right to left in num2             
        for (int j = len2 - 1; j >= 0; j--)
        {
            // Take current digit of second number
            int n2 = num2.charAt(j) - '0';
 
            // Multiply with current digit of first number
            // and add result to previously stored result
            // charAt current position. 
            int sum = n1 * n2 + result[i_n1 + i_n2] + carry;
 
            // Carry for next itercharAtion
            carry = sum / 10;
 
            // Store result
            result[i_n1 + i_n2] = sum % 10;
 
            i_n2++;
        }
 
        // store carry in next cell
        if (carry > 0)
            result[i_n1 + i_n2] += carry;
 
        // To shift position to left after every
        // multipliccharAtion of a digit in num1.
        i_n1++;
    }
 
    // ignore '0's from the right
    int i = result.length - 1;
    while (i >= 0 && result[i] == 0)
    i--;
 
    // If all were '0's - means either both 
    // or one of num1 or num2 were '0'
    if (i == -1)
    return "0";
 
    // genercharAte the result String
    String s = "";
     
    while (i >= 0)
        s += (result[i--]);
 
    return s;
}
 
// Driver code
public static void main(String[] args) 
{
    String str1 = "1235421415454545454545454544";
    String str2 = "1714546546546545454544548544544545";
 
    if ((str1.charAt(0) == '-' || str2.charAt(0) == '-') && 
        (str1.charAt(0) != '-' || str2.charAt(0) != '-'))
        System.out.print("-");
 
    if (str1.charAt(0) == '-')
        str1 = str1.substring(1);
   
    if (str2.charAt(0) == '-')
        str2 = str2.substring(1);
 
    System.out.println(multiply(str1, str2));
}
}
 
// This code is contributed by ankush_953

Python3

# Python3 program to multiply two numbers 
# represented as strings.
 
# Multiplies str1 and str2, and prints result.
def multiply(num1, num2):
    len1 = len(num1)
    len2 = len(num2)
    if len1 == 0 or len2 == 0:
        return "0"
 
    # will keep the result number in vector
    # in reverse order
    result = [0] * (len1 + len2)
     
    # Below two indexes are used to 
    # find positions in result.
    i_n1 = 0
    i_n2 = 0
 
    # Go from right to left in num1
    for i in range(len1 - 1, -1, -1):
        carry = 0
        n1 = ord(num1[i]) - 48
 
        # To shift position to left after every
        # multiplication of a digit in num2
        i_n2 = 0
 
        # Go from right to left in num2
        for j in range(len2 - 1, -1, -1):
             
            # Take current digit of second number
            n2 = ord(num2[j]) - 48
         
            # Multiply with current digit of first number
            # and add result to previously stored result
            # at current position.
            summ = n1 * n2 + result[i_n1 + i_n2] + carry
 
            # Carry for next iteration
            carry = summ // 10
 
            # Store result
            result[i_n1 + i_n2] = summ % 10
 
            i_n2 += 1
 
            # store carry in next cell
        if (carry > 0):
            result[i_n1 + i_n2] += carry
 
            # To shift position to left after every
            # multiplication of a digit in num1.
        i_n1 += 1
         
        # print(result)
 
    # ignore '0's from the right
    i = len(result) - 1
    while (i >= 0 and result[i] == 0):
        i -= 1
 
    # If all were '0's - means either both or
    # one of num1 or num2 were '0'
    if (i == -1):
        return "0"
 
    # generate the result string
    s = ""
    while (i >= 0):
        s += chr(result[i] + 48)
        i -= 1
 
    return s
 
# Driver code
str1 = "1235421415454545454545454544"
str2 = "1714546546546545454544548544544545"
 
if((str1[0] == '-' or str2[0] == '-') and
   (str1[0] != '-' or str2[0] != '-')):
    print("-", end = '')
 
 
if(str1[0] == '-' and str2[0] != '-'):
    str1 = str1[1:]
elif(str1[0] != '-' and str2[0] == '-'):
    str2 = str2[1:]
elif(str1[0] == '-' and str2[0] == '-'):
    str1 = str1[1:]
    str2 = str2[1:]
print(multiply(str1, str2))
 
# This code is contributed by ankush_953

C#

// C# program to multiply two numbers 
// represented as Strings. 
using System;
 
class GFG 
{ 
     
// Multiplies str1 and str2, and prints result. 
static String multiply(String num1, String num2) 
{ 
    int len1 = num1.Length; 
    int len2 = num2.Length; 
    if (len1 == 0 || len2 == 0) 
        return "0"; 
 
    // will keep the result number in vector 
    // in reverse order 
    int []result = new int[len1 + len2]; 
 
    // Below two indexes are used to 
    // find positions in result. 
    int i_n1 = 0; 
    int i_n2 = 0; 
    int i;
     
    // Go from right to left in num1 
    for (i = len1 - 1; i >= 0; i--) 
    { 
        int carry = 0; 
        int n1 = num1[i] - '0'; 
 
        // To shift position to left after every 
        // multipliccharAtion of a digit in num2 
        i_n2 = 0; 
         
        // Go from right to left in num2             
        for (int j = len2 - 1; j >= 0; j--) 
        { 
            // Take current digit of second number 
            int n2 = num2[j] - '0'; 
 
            // Multiply with current digit of first number 
            // and add result to previously stored result 
            // charAt current position. 
            int sum = n1 * n2 + result[i_n1 + i_n2] + carry; 
 
            // Carry for next itercharAtion 
            carry = sum / 10; 
 
            // Store result 
            result[i_n1 + i_n2] = sum % 10; 
 
            i_n2++; 
        } 
 
        // store carry in next cell 
        if (carry > 0) 
            result[i_n1 + i_n2] += carry; 
 
        // To shift position to left after every 
        // multipliccharAtion of a digit in num1. 
        i_n1++; 
    } 
 
    // ignore '0's from the right 
    i = result.Length - 1; 
    while (i >= 0 && result[i] == 0) 
    i--; 
 
    // If all were '0's - means either both 
    // or one of num1 or num2 were '0' 
    if (i == -1) 
    return "0"; 
 
    // genercharAte the result String 
    String s = ""; 
     
    while (i >= 0) 
        s += (result[i--]); 
 
    return s; 
} 
 
// Driver code 
public static void Main(String[] args) 
{ 
    String str1 = "1235421415454545454545454544"; 
    String str2 = "1714546546546545454544548544544545"; 
 
    if ((str1[0] == '-' || str2[0] == '-') && 
        (str1[0] != '-' || str2[0] != '-')) 
        Console.Write("-"); 
 
    if (str1[0] == '-' && str2[0] != '-') 
    { 
        str1 = str1.Substring(1); 
    } 
    else if (str1[0] != '-' && str2[0] == '-') 
    { 
        str2 = str2.Substring(1); 
    } 
    else if (str1[0] == '-' && str2[0] == '-') 
    { 
        str1 = str1.Substring(1); 
        str2 = str2.Substring(1); 
    } 
    Console.WriteLine(multiply(str1, str2)); 
} 
}
 
// This code is contributed by Rajput-Ji

Javascript

// JavaScript program to multiply two numbers 
// represented as strings.
 
// Multiplies str1 and str2, and prints result.
function multiply(num1, num2)
{
    let len1 = num1.length;
    let len2 = num2.length;
    if (len1 == 0 || len2 == 0)
        return "0"
 
    // will keep the result number in vector
    // in reverse order
    let result = new Array(len1 + len2).fill(0)
     
    // Below two indexes are used to 
    // find positions in result.
    let i_n1 = 0
    let i_n2 = 0
 
    // Go from right to left in num1
    for (var i = len1 - 1; i > -1 ; i --)
    {
        let carry = 0
        let n1 = (num1[i]).charCodeAt(0) - 48
 
        // To shift position to left after every
        // multiplication of a digit in num2
        i_n2 = 0
 
        // Go from right to left in num2
        for (var j = len2 - 1; j > -1; j--)
        {
            // Take current digit of second number
            let n2 = (num2[j]).charCodeAt(0) - 48
         
            // Multiply with current digit of first number
            // and add result to previously stored result
            // at current position.
            let summ = n1 * n2 + result[i_n1 + i_n2] + carry
 
            // Carry for next iteration
            carry = Math.floor(summ / 10)
 
            // Store result
            result[i_n1 + i_n2] = summ % 10
 
            i_n2 += 1
        }
 
        // store carry in next cell
        if (carry > 0)
            result[i_n1 + i_n2] += carry
 
        // To shift position to left after every
        // multiplication of a digit in num1.
        i_n1 += 1
         
        // print(result)
    }
    // ignore '0's from the right
    i = result.length - 1
    while (i >= 0 && result[i] == 0)
        i -= 1
 
    // If all were '0's - means either both or
    // one of num1 or num2 were '0'
    if (i == -1)
        return "0"
 
    // generate the result string
    let s = ""
    while (i >= 0)
    {
        s += String.fromCharCode(result[i] + 48)
        i -= 1
    }
 
    return s
    }
 
 
// Driver code
let str1 = "1235421415454545454545454544"
let str2 = "1714546546546545454544548544544545"
 
if((str1[0] == '-' || str2[0] == '-') && 
   (str1[0] != '-' || str2[0] != '-'))
    process.stdout.write("-")
 
 
if(str1[0] == '-' && str2[0] != '-')
    str1.shift()
else if(str1[0] != '-' && str2[0] == '-')
    str2.shift()
else if(str1[0] == '-' && str2[0] == '-')
{
    str1.shift()
    str2.shift()
}
 
console.log(multiply(str1, str2))
 
// This code is contributed by phasing17

Output:

2118187521397235888154583183918321221520083884298838480662480

The above code is adapted from the code provided by Gaurav.
Time Complexity: O(m*n), where m and n are length of two number that need to be multiplied.
Auxiliary Space: O(m+n), where m and n are length of two number that need to be multiplied.

The Way to understand:

The Approach:

Compute the ones-digit, then the tens-digit, then the hundreds-digit, etc. For example when multiplying 1234 with 5678, the thousands-digit of the product is 4*5 + 3*6 + 2*7 + 1*8 (plus what got carried from the hundreds-digit).

C++

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
 
int main() {
   string a = "1235421415454545454545454544";
   string b = "1714546546546545454544548544544545";
   if (a=="0" || b=="0"){
      cout<<0<<endl;
      return 0;
   }
    int m = a.size() - 1, n = b.size() - 1, carry = 0;
    string product;
    for (int i=0; i<=m+n || carry; ++i) {
        for (int j=max(0, i-n); j<=min(i, m); ++j)
            carry += (a[m-j] - '0') * (b[n-i+j] - '0');
        product += carry % 10 + '0';
        carry /= 10;
    }
    reverse(begin(product), end(product));
   cout<<"The Product is: ";
   cout<<product<<endl;
  //code given by sanket gode 
    return 0;
}

Java

import java.util.*;
public class Main {
    public static void main(String[] args)
    {
        String a = "1235421415454545454545454544";
        String b = "1714546546546545454544548544544545";
        if (a.equals("0") || b.equals("0")) {
            System.out.println("0");
            return;
        }
        int m = a.length() - 1, n = b.length() - 1,
            carry = 0;
        String product = "";
        for (int i = 0; i <= m + n || carry != 0; ++i) {
            for (int j = Math.max(0, i - n);
                 j <= Math.min(i, m); ++j) {
                carry += (a.charAt(m - j) - '0')
                         * (b.charAt(n - i + j) - '0');
            }
            product += (char)(carry % 10 + '0');
            carry /= 10;
        }
        product = new StringBuilder(product)
                      .reverse()
                      .toString();
        System.out.println("The Product is: " + product);
    }
}

Python3

def multiply_strings(a, b):
    if a == "0" or b == "0":
        return "0"
     
    m, n = len(a) - 1, len(b) - 1
    carry = 0
    product = ""
    for i in range(0, m+n+1):
        for j in range(max(0, i-n), min(i, m)+1):
            carry += (ord(a[m-j]) - 48) * (ord(b[n-i+j]) - 48)
        product += str(carry % 10)
        carry //= 10
    return product[::-1]
 
if __name__ == '__main__':
    a = "1235421415454545454545454544"
    b = "1714546546546545454544548544544545"
    product = multiply_strings(a, b)
    print("The Product is: " + product)

Javascript

function multiplyStrings(a, b) {
  if (a === "0" || b === "0") {
    return "0";
  }
 
  let m = a.length - 1;
  let n = b.length - 1;
  let carry = 0;
  let product = "";
   
  for (let i = 0; i <= m + n; i++) {
    for (let j = Math.max(0, i - n); j <= Math.min(i, m); j++) {
      carry += (a[m - j].charCodeAt(0) - 48) * (b[n - i + j].charCodeAt(0) - 48);
    }
    product += (carry % 10).toString();
    carry = Math.floor(carry / 10);
  }
 
  return product.split("").reverse().join("");
}
 
// Example usage
const a = "1235421415454545454545454544";
const b = "1714546546546545454544548544544545";
const product = multiplyStrings(a, b);
console.log("The Product is: " + product);

C#

using System;
 
public class Mainn {
    public static void Main(string[] args) {
        string a = "1235421415454545454545454544";
        string b = "1714546546546545454544548544544545";
        if (a.Equals("0") || b.Equals("0")) {
            Console.WriteLine("0");
            return;
        }
        int m = a.Length - 1, n = b.Length - 1,
            carry = 0;
        string product = "";
        for (int i = 0; i <= m + n || carry != 0; ++i) {
            for (int j = Math.Max(0, i - n);
                 j <= Math.Min(i, m); ++j) {
                carry += (a[m - j] - '0')
                         * (b[n - i + j] - '0');
            }
            product += (char)(carry % 10 + '0');
            carry /= 10;
        }
        char[] charArray = product.ToCharArray();
        Array.Reverse(charArray);
        product = new string(charArray);
        Console.WriteLine("The Product is: " + product);
    }
}

Time Complexity: O(m*n), where m and n are length of two number that need to be multiplied.
Auxiliary Space: O(m+n), where m and n are length of two number that need to be multiplied.

Method 2:

C++

// Include header file
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    string num1 = "1235421415454545454545454544";
    string tempnum1 = num1;
    string num2 = "1714546546546545454544548544544545";
    string tempnum2 = num2;
    // Check condition if one string is negative
    if (num1[0] == '-' && num2[0] != '-') {
        num1 = num1.substr(1);
    }
    else if (num1[0] != '-' && num2[0] == '-') {
        num2 = num2.substr(1);
    }
    else if (num1[0] == '-' && num2[0] == '-') {
        num1 = num1.substr(1);
        num2 = num2.substr(1);
    }
    string s1 = num1;
    string s2 = num2;
    reverse(s1.begin(), s1.end());
    reverse(s2.begin(), s2.end());
 
    vector<int> m(s1.length() + s2.length());
    // Go from right to left in num1
    for (int i = 0; i < s1.length(); i++) {
        // Go from right to left in num2
        for (int j = 0; j < s2.length(); j++) {
            m[i + j]
                = m[i + j] + (s1[i] - '0') * (s2[j] - '0');
        }
    }
    string product = "";
    // Multiply with current digit of first number
    // and add result to previously stored product
    // at current position.
    for (int i = 0; i < m.size(); i++) {
        int digit = m[i] % 10;
        int carry = m[i] / 10;
        if (i + 1 < m.size()) {
            m[i + 1] = m[i + 1] + carry;
        }
        product = to_string(digit) + product;
    }
    // ignore '0's from the right
    while (product.length() > 1 && product[0] == '0') {
        product = product.substr(1);
    }
    // Check condition if one string is negative
    if (tempnum1[0] == '-' && tempnum2[0] != '-') {
        product = "-" + product;
    }
    else if (tempnum1[0] != '-' && tempnum2[0] == '-') {
        product = "-" + product;
    }
 
    cout << "Product of the two numbers is :"
         << "\n"
         << product << endl;
}
 
// This code is contributed by Aarti_Rathi

Java

// Java program to multiply two numbers represented
// as strings.
import java.util.Scanner;
 
public class StringMultiplication {
    // Driver code
    public static void main(String[] args)
    {
        String num1 = "1235421415454545454545454544";
        String tempnum1 = num1;
        String num2 = "1714546546546545454544548544544545";
        String tempnum2 = num2;
 
        // Check condition if one string is negative
        if (num1.charAt(0) == '-'
            && num2.charAt(0) != '-') {
            num1 = num1.substring(1);
        }
        else if (num1.charAt(0) != '-'
                 && num2.charAt(0) == '-') {
            num2 = num2.substring(1);
        }
        else if (num1.charAt(0) == '-'
                 && num2.charAt(0) == '-') {
            num1 = num1.substring(1);
            num2 = num2.substring(1);
        }
        String s1
            = new StringBuffer(num1).reverse().toString();
        String s2
            = new StringBuffer(num2).reverse().toString();
 
        int[] m = new int[s1.length() + s2.length()];
 
        // Go from right to left in num1
        for (int i = 0; i < s1.length(); i++) {
            // Go from right to left in num2
            for (int j = 0; j < s2.length(); j++) {
                m[i + j] = m[i + j]
                           + (s1.charAt(i) - '0')
                                 * (s2.charAt(j) - '0');
            }
        }
 
        String product = new String();
        // Multiply with current digit of first number
        // and add result to previously stored product
        // at current position.
        for (int i = 0; i < m.length; i++) {
            int digit = m[i] % 10;
            int carry = m[i] / 10;
            if (i + 1 < m.length) {
                m[i + 1] = m[i + 1] + carry;
            }
            product = digit + product;
        }
 
        // ignore '0's from the right
        while (product.length() > 1
               && product.charAt(0) == '0') {
            product = product.substring(1);
        }
 
        // Check condition if one string is negative
        if (tempnum1.charAt(0) == '-'
            && tempnum2.charAt(0) != '-') {
            product = new StringBuffer(product)
                          .insert(0, '-')
                          .toString();
        }
        else if (tempnum1.charAt(0) != '-'
                 && tempnum2.charAt(0) == '-') {
            product = new StringBuffer(product)
                          .insert(0, '-')
                          .toString();
        }
        else if (tempnum1.charAt(0) == '-'
                 && tempnum2.charAt(0) == '-') {
            product = product;
        }
        System.out.println("Product of the two numbers is :"
                           + "\n" + product);
    }
}

Python3

# Python3 program to implement the above approach
 
# function to reverse the string
def reverse(s):
    str = ""
    for i in s:
        str = i + str
    return str
 
num1 = "1235421415454545454545454544"
tempnum1 = num1
num2 = "1714546546546545454544548544544545"
tempnum2 = num2
 
# Check condition if one string is negative
if (num1[0] == '-' and num2[0] != '-'):
    num1 = num1[1:]
elif (num1[0] != '-' and num2[0] == '-'):
    num2 = num2[1:]
elif (num1[0] == '-' and num2[0] == '-'):
    num1 = num1[1:]
    num2 = num2[1:]
  
s1 = num1
s2 = num2
s1 = reverse(s1)
s2 = reverse(s2)
m = [0]*(len(s1)+len(s2))
 
# Go from right to left in num1
for i in range(len(s1)):
   
    # Go from right to left in num2
    for j in range(len(s2)):
        m[i + j] = m[i + j] + (ord(s1[i]) - 48) * (ord(s2[j]) - 48)
       
     
product = ""
# Multiply with current digit of first number
# and add result to previously stored product
# at current position.
for i in range(len(m)):
    digit = m[i] % 10
    carry = m[i] // 10
    if (i + 1 < len(m)):
        m[i + 1] = m[i + 1] + carry
    product = str(digit) + product
   
# ignore '0's from the right
while (len(product) > 1 and product[0] == '0'): 
    product = product[1:]
    
#check condition if one string is negative
if (tempnum1[0] == '-' and tempnum2[0] != '-'):
    product = "-" + product
     
elif (tempnum1[0] != '-' and tempnum2[0] == '-'):
    product = "-" + product
     
 
print("Product of the two numbers is :")
print(product)
 
 
# This code is contributed by Abhijeet Kumar(abhijeet19403)

C#

// C# program to multiply two numbers represented
// as strings.
using System;
using System.Text;
using System.Linq;
 
public class GFG{
 
  // Driver Code
  static public void Main (){
    String num1 = "1235421415454545454545454544";
    String tempnum1 = num1;
    String num2 = "1714546546546545454544548544544545";
    String tempnum2 = num2;
 
    // Check condition if one string is negative
    if (num1[0] == '-' && num2[0] != '-') {
      num1 = num1.Substring(1);
    }else{
      if (num1[0] != '-' && num2[0] == '-') {
        num2 = num2.Substring(1);
      }else{
        if (num1[0] == '-' && num2[0] == '-') {
          num1 = num1.Substring(1);
          num2 = num2.Substring(1);
        }
      }
    }
 
    String s1 = new string(num1.Reverse().ToArray());
    String s2 = new string(num2.Reverse().ToArray());
 
    int[] m = new int[s1.Length + s2.Length];
 
    // Go from right to left in num1
    for (int i = 0; i < s1.Length; i++) {
      // Go from right to left in num2
      for (int j = 0; j < s2.Length; j++) {
        int x = int.Parse((s1[i]-'0').ToString());
        int y = int.Parse((s2[j]-'0').ToString());
        m[i + j] += (x*y);
      }
    }
 
    String product = "";
    // Multiply with current digit of first number
    // and add result to previously stored product
    // at current position.
    for (int i = 0; i < m.Length; i++) {
      int digit = m[i] % 10;
      int carry = m[i] / 10;
      if (i + 1 < m.Length) {
        m[i + 1] += carry;
      }
      product = digit.ToString() + product;
    }
 
    // ignore '0's from the right
    while (product.Length > 1 && product[0] == '0') {
      product = product.Substring(1);
    }
 
 
    // Check condition if one string is negative
    if (tempnum1[0] == '-' && tempnum2[0] != '-') {
      product = new StringBuilder(product).Insert(0, '-').ToString();
    }else{
      if (tempnum1[0] != '-' && tempnum2[0] == '-') {
        product = new StringBuilder(product).Insert(0, '-').ToString();
      }
    } 
    Console.Write("Product of the two numbers is :\n" + product);
  }
}
 
// This code is contributed by shruti456rawal

Javascript

// Javascript program to implement the approach
let num1 = "1235421415454545454545454544";
let tempnum1 = num1;
let num2 = "1714546546546545454544548544544545";
let tempnum2 = num2;
 
// Check condition if one string is negative
if (num1[0] == '-' && num2[0] != '-') {
    num1 = num1.substring(1);
}
else if (num1[0] != '-' && num2[0] == '-') {
    num2 = num2.substring(1);
}
else if (num1[0] == '-' && num2[0] == '-') {
    num1 = num1.substring(1);
    num2 = num2.substring(1);
}
 
let s1 = num1.split("");
let s2 = num2.split("");
 
s1.reverse();
s2.reverse();
 
let m = new Array(s1.length + s2.length).fill(0);
 
// Go from right to left in num1
for (var i = 0; i < s1.length; i++)
{
 
    // Go from right to left in num2
    for (var j = 0; j < s2.length; j++) {
        m[i + j] = m[i + j]
                   + (parseInt(s1[i]) * (parseInt(s2[j])));
    }
}
let product = "";
 
// Multiply with current digit of first number
// and add result to previously stored product
// at current position.
for (var i = 0; i < m.length; i++) {
    let digit = m[i] % 10;
    let carry = Math.floor(m[i] / 10);
    if (i + 1 < m.length) {
        m[i + 1] = m[i + 1] + carry;
    }
    product = digit.toString() + product;
}
 
// ignore '0's from the right
while (product.length > 1 && product[0] == '0') {
    product = product.substring(1);
}
 
// Check condition if one string is negative
if (tempnum1[0] == '-' && tempnum2[0] != '-') {
    product = "-" + product;
}
else if (tempnum1[0] != '-' && tempnum2[0] == '-') {
    product = "-" + product;
}
 
console.log("Product of the two numbers is :");
console.log(product);
 
// This code is contributed by phasing17

Output

Product of the two numbers is :
2118187521397235888154583183918321221520083884298838480662480

Time Complexity: O(m*n), where m and n are length of two number that need to be multiplied.
Auxiliary Space: O(m+n), where m and n are length of two number that need to be multiplied.

Method 3:

Convert the two input numbers from strings to lists of integers.
A list with zeros.
Iterate over each digit in the second number (num2) from right to left.
For each digit, multiply it with each digit in the first number num1, and add the result in the result list.
Convert the result list to a string.

C++

#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
 
string multiply(string num1, string num2) {
    // Convert the input numbers from strings to vectors of integers
    vector<int> vec1(num1.size());
    for (int i = 0; i < num1.size(); i++) {
        vec1[i] = num1[num1.size() - i - 1] - '0';
    }
    vector<int> vec2(num2.size());
    for (int i = 0; i < num2.size(); i++) {
        vec2[i] = num2[num2.size() - i - 1] - '0';
    }
 
    // Initialize the result vector with zeros
    vector<int> result(vec1.size() + vec2.size());
 
    // Multiply each digit in vec2 with vec1 and add the result to the appropriate position in the result vector
    for (int i = 0; i < vec2.size(); i++) {
        int carry = 0;
        for (int j = 0; j < vec1.size(); j++) {
            int product = vec1[j] * vec2[i] + carry + result[i + j];
            carry = product / 10;
            result[i + j] = product % 10;
        }
        result[i + vec1.size()] = carry;
    }
 
    // Remove leading zeros from the result vector and convert it back to a string
    while (result.size() > 1 && result.back() == 0) {
        result.pop_back();
    }
    string str(result.size(), '0');
    for (int i = 0; i < result.size(); i++) {
        str[result.size() - i - 1] = result[i] + '0';
    }
    return str;
}
 
int main() {
    string num1 = "4154";
    string num2 = "51454";
    cout << multiply(num1, num2) << endl;
 
    num1 = "654154154151454545415415454";
    num2 = "63516561563156316545145146514654";
    cout << multiply(num1, num2) << endl;
 
    return 0;
}

Java

public class MultiplyStrings {
    public static String multiply(String num1, String num2) {
        int[] n1 = new int[num1.length()];
        int[] n2 = new int[num2.length()];
 
        for (int i = 0; i < num1.length(); i++) {
            n1[i] = num1.charAt(num1.length() - 1 - i) - '0';
        }
 
        for (int i = 0; i < num2.length(); i++) {
            n2[i] = num2.charAt(num2.length() - 1 - i) - '0';
        }
 
        int[] result = new int[num1.length() + num2.length()];
 
        for (int i = 0; i < n2.length; i++) {
            int carry = 0;
            for (int j = 0; j < n1.length; j++) {
                int product = n1[j] * n2[i] + carry + result[i + j];
                carry = product / 10;
                result[i + j] = product % 10;
            }
            result[i + n1.length] = carry;
        }
 
        StringBuilder sb = new StringBuilder();
        int i = result.length - 1;
        while (i > 0 && result[i] == 0) {
            i--;
        }
        while (i >= 0) {
            sb.append(result[i--]);
        }
 
        return sb.toString();
    }
 
    public static void main(String[] args) {
        String num1 = "4154";
        String num2 = "51454";
        System.out.println(multiply(num1, num2)); // Output: 213739916
 
        num1 = "654154154151454545415415454";
        num2 = "63516561563156316545145146514654";
        System.out.println(multiply(num1, num2)); // Output: 41549622603955309777243716069997997007620439937711509062916
    }
}

Python3

def multiply(num1, num2):
    # Convert the input numbers from strings to lists of integers
    num1 = [int(digit) for digit in num1][::-1]
    num2 = [int(digit) for digit in num2][::-1]
 
    # Initialize the result list with zeros
    result = [0] * (len(num1) + len(num2))
 
    # Multiply each digit in num2 with num1 and add the result to the appropriate position in the result list
    for i, digit2 in enumerate(num2):
        carry = 0
        for j, digit1 in enumerate(num1):
            product = digit1 * digit2 + carry + result[i + j]
            carry = product // 10
            result[i + j] = product % 10
        result[i + len(num1)] = carry
 
    # Remove leading zeros from the result list and convert it back to a string
    result = result[::-1]
    while len(result) > 1 and result[-1] == 0:
        result.pop()
    return ''.join(str(digit) for digit in result)
# Example 1
num1 = "4154"
num2 = "51454"
print(multiply(num1, num2))
# Output: "213739916"
 
# Example 2
num1 = "654154154151454545415415454"
num2 = "63516561563156316545145146514654"
print(multiply(num1, num2))
# Output: "41549622603955309777243716069997997007620439937711509062916"

Javascript

function multiply(num1, num2) {
    // Convert the input numbers from strings to arrays of integers
    let vec1 = num1.split("").reverse().map(Number);
    let vec2 = num2.split("").reverse().map(Number);
 
    // Initialize the result array with zeros
    let result = Array(vec1.length + vec2.length).fill(0);
 
    // Multiply each digit in vec2 with vec1 and add the result to the appropriate position in the result array
    for (let i = 0; i < vec2.length; i++) {
        let carry = 0;
        for (let j = 0; j < vec1.length; j++) {
            let product = vec1[j] * vec2[i] + carry + result[i + j];
            carry = Math.floor(product / 10);
            result[i + j] = product % 10;
        }
        result[i + vec1.length] = carry;
    }
 
    // Remove leading zeros from the result array and convert it back to a string
    while (result.length > 1 && result[result.length - 1] === 0) {
        result.pop();
    }
    let str = result.reverse().join("");
    return str;
}
 
       let Num1 = "4154";
       let Num2 = "51454";
       console.log(multiply(Num1, Num2));
      let num1 = "654154154151454545415415454";
      let num2 = "63516561563156316545145146514654";
console.log(multiply(num1, num2));

C#

using System;
using System.Linq;
 
public class Program
{
    public static string Multiply(string num1, string num2)
    {
        // Convert the input numbers from strings to arrays of integers
        int[] vec1 = num1.Reverse().Select(c => c - '0').ToArray();
        int[] vec2 = num2.Reverse().Select(c => c - '0').ToArray();
 
        // Initialize the result array with zeros
        int[] result = new int[vec1.Length + vec2.Length];
 
        // Multiply each digit in vec2 with vec1 and add the result to the appropriate position in the result array
        for (int i = 0; i < vec2.Length; i++)
        {
            int carry = 0;
            for (int j = 0; j < vec1.Length; j++)
            {
                int product = vec1[j] * vec2[i] + carry + result[i + j];
                carry = product / 10;
                result[i + j] = product % 10;
            }
            result[i + vec1.Length] = carry;
        }
 
        // Remove leading zeros from the result array and convert it back to a string
        while (result.Length > 1 && result[result.Length - 1] == 0)
        {
            Array.Resize(ref result, result.Length - 1);
        }
        string str = new string(result.Reverse().Select(d => (char)(d + '0')).ToArray());
        return str;
    }
 
    public static void Main()
    {
        string num1 = "4154";
        string num2 = "51454";
        Console.WriteLine(Multiply(num1, num2));
 
        string num3 = "654154154151454545415415454";
        string num4 = "63516561563156316545145146514654";
        Console.WriteLine(Multiply(num3, num4));
    }
}

Output

213739916
41549622603955309777243716069997997007620439937711509062916

Time Complexity: O(m*n), where m and n are length of two number that need to be multiplied.
Auxiliary Space: O(m+n), where m and n are length of two number that need to be multiplied.

Related Article :
Karatsuba algorithm for fast multiplication
This article is contributed by Aditya Kumar. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.

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!

Multiply Large Numbers represented as Strings

C++

Java

Python3

C#

Javascript

C++

Java

Python3

Javascript

C#

C++

Java

Python3

C#

Javascript

C++

Java

Python3

Javascript

C#

LEAVE A REPLY Cancel reply

Most Popular

Recent Comments

EDITOR PICKS

POPULAR POSTS

POPULAR CATEGORY

ABOUT US

FOLLOW US