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 methodclass 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 bdef 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 codestr1 = "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 methodusing 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
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
