Multiply Large Numbers using Grid Method

Namachila 2 minutes ago

0 0 8 minutes read

Given two large numbers A and B, the task is to find the product of these two numbers using Grid Method.
Examples:

Input: A = 23, B = 15
Output: 345
Input: A = 321, B = 69
Output: 22149

Approach:

Create 2D Array of N Rows and M columns where N is number of digit in first number and M is number of digit in second number.

Multiply each element of row with each element of column

Total Number of Diagonal = Row + Columns – 1
= 2 + 2 -1
= 3

Create 1D Array which contains the addition of elements in each diagonal
d3 = 2
d2 = 13
d1 = 15
Diagonal sum[] = {2, 13, 15}
output = “”
total = 0
i = DiagonalSum.length – 1

Repeat in reverse order of insertion except for first element in Diagonal Sum[] Array
total = total + DiagonalSum[i]. If total contain more than single digit then total = all digit from total except unit place digit. output = unit_place_digit + output else total = 0

total = total + DiagonalSum[0]
output = total + output

Below is the implementation of the above approach:

Java

// Java program to multiply Large
// numbers using the grid method
 
class GFG {
 
    // Function to return the multiplication of a and b
    public static String multiply(String a, String b)
    {
        boolean flag1 = false;
        boolean flag2 = false;
        a = a.trim();
        b = b.trim();
 
        // To check whether numbers are
        // negative or positive
        if (a.charAt(0) == '-') {
            a = a.replace("-", "");
            flag1 = true;
        }
        if (b.charAt(0) == '-') {
            b = b.replace("-", "");
            flag2 = true;
        }
 
        // To store the result of
        // multiplication
        String out = "";
 
        // To create matrix(Grid) of row * column
        int row = a.length();
        int column = b.length();
        int[][] c = new int[row][column];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                int n1
                    = Character
                          .getNumericValue(
                              a.charAt(i));
                int n2
                    = Character
                          .getNumericValue(
                              b.charAt(j));
                c[i][j] = n1 * n2;
            }
        }
 
        // To create 1D array of (row+column-1) size
        // which is equal to total number
        // of diagonal in matrix
        int[] sum = new int[row + column - 1];
        int m = 0;
 
        // To add elements of each diagonals
        for (int i = 0; i < row; i++) {
            int k = i;
            int add = 0;
 
            for (int j = 0; j < column && k >= 0; j++, k--) {
                add = add + c[k][j];
            }
            sum[m] = add;
            m = m + 1;
        }
        for (int k = 1; k < column; k++) {
            int i = row - 1;
            int j = k;
            int add = 0;
            while (j < column && i >= 0) {
                add = add + c[i][j];
                j = j + 1;
                i = i - 1;
            }
            sum[m] = add;
            m = m + 1;
        }
 
        // To check both numbers are not
        // single digit number
        if (sum.length != 1) {
 
            String temp
                = Integer
                      .toString(
                          sum[sum.length - 1]);
            int t = 0;
 
            // Repeat element in "sum" Array
            // in reverse order
            for (int n = sum.length - 1; n >= 1; n--) {
 
                // Add element with result "t"
                t = t + sum[n];
 
                // Convert integer element into String
                // which is sum of all elements
                // of particular diagonal
                temp = Integer.toString(t);
                if (temp.length() > 1) {
 
                    // If the number contains more than a single-digit
                    // then copy all the digit into "temp"
                    // as String except for the unit place digit
                    String str = temp.substring(0, temp.length() - 1);
                    t = Integer.parseInt(str);
                }
                else {
                    t = 0;
                }
 
                // Concat unit place digit at the
                // beginning of String "out"
                out = temp.charAt(temp.length() - 1) + out;
            }
 
            // Add first element with result "t"
            t = t + sum[0];
            temp = Integer.toString(t);
            out = temp + out;
        }
        else {
            out = out + sum[0];
        }
 
        StringBuffer s = new StringBuffer(out);
 
        // To remove Zero's from the beginning
        // of the multiplication result
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) == '0') {
                s.deleteCharAt(i);
                i = i - 1;
            }
            else {
                break;
            }
        }
        out = s.toString();
 
        // Check if the result of multiplication
        // operation is zero
        if (!out.equals("0")) {
 
            // If one of two numbers is negative then
            // assign minus sign to the result of
            // multiplication operation
            if (flag1 == true && flag2 == false) {
                out = "-" + out;
            }
            else if (flag2 == true && flag1 == false) {
                out = "-" + out;
            }
        }
        return out;
    }
 
    // Driver code
    public static void main(String args[])
    {
        String str1 = "123456789";
        String str2 = "987654321";
        System.out.println(multiply(str1, str2));
 
        str1 = "1235421415454545454545454544";
        str2 = "1714546546546545454544548544544545";
        System.out.println(multiply(str1, str2));
    }
}

Python3

# Python3 program to multiply Large
# numbers using the grid method
 
# Function to return the multiplication of a and b
def multiply(a, b):
 
    flag1 = False;
    flag2 = False;
    a = a.strip()
    b = b.strip()
 
    # To check whether numbers are
    # negative or positive
    if (a[0] == '-') :
        a = a.replace("-", "");
        flag1 = True;
     
    if (b[0] == '-'): 
        b = b.replace("-", "");
        flag2 = True;
     
    # To store the result of
    # multiplication
    out1 = "";
 
    # To create matrix(Grid) of row * column
    row = len(a);
    column = len(b);
    c =[ [0 for _ in range(column)] for __ in range(row)]
    for i in range(row):
        for j in range(column):
            n1 = int(a[i]);
            n2 = int(b[j]);
            c[i][j] = n1 * n2;
         
    # To create 1D array of (row+column-1) size
    # which is equal to total number
    # of diagonal in matrix
    sum1 = [0 for _ in range(row + column - 1)];
    m = 0;
 
    # To add elements of each diagonals
    for i in range(row):
        k = i;
        add = 0;
         
        j = 0
        while j < column and k >= 0:
            add = add + c[k][j];
            j += 1
            k -= 1
         
        sum1[m] = add;
        m = m + 1;
     
    for k in range(1, column): 
        i = row - 1;
        j = k;
        add = 0;
        while (j < column and i >= 0): 
            add = add + c[i][j];
            j = j + 1;
            i = i - 1;
         
        sum1[m] = add;
        m = m + 1;
     
    # To check both numbers are not
    # single digit number
    if (len(sum1) != 1) :
 
        temp  = str(sum1[len(sum1) - 1]);
        t = 0;
 
        # Repeat element in "sum1" Array
        # in reverse order
        for n in range(len(sum1) - 1, 0, -1):
 
            # Add element with result "t"
            t = t + sum1[n];
 
            # Convert integer element into string
            # which is sum1 of all elements
            # of particular diagonal
            temp = str(t);
            if (len(temp) > 1) :
 
                # If the number contains more than a
                # single-digit then copy all the digit
                # into "temp" as except for the
                # unit place digit
                str1 = temp[0 : len(temp) - 1]
                t = int(str1);
             
            else :
                t = 0;
             
            # Concat unit place digit at the
            # beginning of "out1"
            out1 = temp[len(temp) - 1] + out1;
         
        # Add first element with result "t"
        t = t + sum1[0];
        temp = str(t);
        out1 = temp + out1;
     
    else :
        out1 = out1 + sum1[0];
     
 
    s = out1
 
    # To remove Zero's from the beginning
    # of the multiplication result
    for i in range(len(s) - 1):
        if (s[i] == '0') :
            s = s[:i] + s[i + 1:]
            i = i - 1;
         
        else :
            break;
         
     
    out1 = s
 
    # Check if the result of multiplication
    # operation is zero
    if (out1 != "0"):
 
        # If one of two numbers is negative then
        # assign minus sign to the result of
        # multiplication operation
        if (flag1 == True and flag2 == False) :
            out1 = "-" + out1;
         
        elif (flag2 == True and flag1 == False) :
            out1 = "-" + out1;
         
     
    return out1;
 
# Driver code
str1 = "123456789";
str2 = "987654321";
print(multiply(str1, str2));
 
str1 = "1235421415454545454545454544";
str2 = "1714546546546545454544548544544545";
print(multiply(str1, str2));
 
# This code is contributed by phasing17            

C#

// C# program to multiply Large
// numbers using the grid method
using System;
using System.Text;
using System.Collections.Generic;
 
class GFG {
 
    // Function to return the multiplication of a and b
    public static string multiply(string a, string b)
    {
        bool flag1 = false;
        bool flag2 = false;
        a = a.Trim();
        b = b.Trim();
 
        // To check whether numbers are
        // negative or positive
        if (a[0] == '-') {
            a = a.Replace("-", "");
            flag1 = true;
        }
        if (b[0] == '-') {
            b = b.Replace("-", "");
            flag2 = true;
        }
 
        // To store the result of
        // multiplication
        string out1 = "";
 
        // To create matrix(Grid) of row * column
        int row = a.Length;
        int column = b.Length;
        int[, ] c = new int[row, column];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                int n1 = a[i] - '0';
                int n2 = b[j] - '0';
                c[i, j] = n1 * n2;
            }
        }
 
        // To create 1D array of (row+column-1) size
        // which is equal to total number
        // of diagonal in matrix
        int[] sum = new int[row + column - 1];
        int m = 0;
 
        // To add elements of each diagonals
        for (int i = 0; i < row; i++) {
            int k = i;
            int add = 0;
 
            for (int j = 0; j < column && k >= 0;
                 j++, k--) {
                add = add + c[k, j];
            }
            sum[m] = add;
            m = m + 1;
        }
        for (int k = 1; k < column; k++) {
            int i = row - 1;
            int j = k;
            int add = 0;
            while (j < column && i >= 0) {
                add = add + c[i, j];
                j = j + 1;
                i = i - 1;
            }
            sum[m] = add;
            m = m + 1;
        }
 
        // To check both numbers are not
        // single digit number
        if (sum.Length != 1) {
 
            string temp
                = Convert.ToString(sum[sum.Length - 1]);
            int t = 0;
 
            // Repeat element in "sum" Array
            // in reverse order
            for (int n = sum.Length - 1; n >= 1; n--) {
 
                // Add element with result "t"
                t = t + sum[n];
 
                // Convert integer element into string
                // which is sum of all elements
                // of particular diagonal
                temp = Convert.ToString(t);
                if (temp.Length > 1) {
 
                    // If the number contains more than a
                    // single-digit then copy all the digit
                    // into "temp" as string except for the
                    // unit place digit
                    string str = temp.Substring(
                        0, temp.Length - 1);
                    t = Convert.ToInt32(str);
                }
                else {
                    t = 0;
                }
 
                // Concat unit place digit at the
                // beginning of string "out1"
                out1 = temp[temp.Length - 1] + out1;
            }
 
            // Add first element with result "t"
            t = t + sum[0];
            temp = Convert.ToString(t);
            out1 = temp + out1;
        }
        else {
            out1 = out1 + sum[0];
        }
 
        StringBuilder s = new StringBuilder(out1);
 
        // To remove Zero's from the beginning
        // of the multiplication result
        for (int i = 0; i < s.Length - 1; i++) {
            if (s[i] == '0') {
                s.Remove(i, 1);
                i = i - 1;
            }
            else {
                break;
            }
        }
        out1 = s.ToString();
 
        // Check if the result of multiplication
        // operation is zero
        if (!out1.Equals("0")) {
 
            // If one of two numbers is negative then
            // assign minus sign to the result of
            // multiplication operation
            if (flag1 == true && flag2 == false) {
                out1 = "-" + out1;
            }
            else if (flag2 == true && flag1 == false) {
                out1 = "-" + out1;
            }
        }
        return out1;
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        string str1 = "123456789";
        string str2 = "987654321";
        Console.WriteLine(multiply(str1, str2));
 
        str1 = "1235421415454545454545454544";
        str2 = "1714546546546545454544548544544545";
        Console.WriteLine(multiply(str1, str2));
    }
}
 
// This code is contributed by phasing17

Output:
121932631112635269
2118187521397235888154583183918321221520083884298838480662480

Time Complexity: O(row * column)

Auxiliary Space: O(row * column)

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 zambiatek!