Find the missing digit in given product of large positive integers
Given two large integers in form of strings A and B and their product also in form of string C such that one digit of the product is replaced with X, the task is to find the replaced digit in the product C.
Examples:
Input: A = 51840, B = 273581, C = 1418243×040
Output: 9
Explanation:
The product of integer A and B is 51840 * 273581 = 14182439040. On comparing it with C, it can be concluded that the replaced digit was 9. Therefore, print 9.Input: A = 123456789, B = 987654321, C = 12193263111×635269
Output: 2
Naive Approach: The simplest approach to solve the given problem is to find the product of two large integers A and B using the approach discussed in this article and then comparing it with C to find the resultant missing digit X.
Time Complexity: O((log10A)*(log10B))
Auxiliary Space: O(log10A + log10B)
Efficient Approach: The above approach can also be optimized by using the following observations:
Suppose N is an integer such that N = amam-1am-2 …….a2a1a0 where ax represents the xth digit. Now, N can be represented as:
=> N = am * 10m + am-1 * 10m-1 + ………… + a1 * 10 + a0Performing the modulo operation with 11 in the above equation:
=> N (mod 11) = am * 10m + am-1 * 10m-1 + ………… + a1 * 10 + a0 (mod 11)
=> N (mod 11) = am(-1)m + am-1(-1)m-1 + ……….. + a1(-1) + a0 (mod 11) [Since 10 ? -1 (mod 11)]
=> N (mod 11) = T (mod 11) where T = a0 – a1 + a2 …… + (-1)mam
Therefore, from the above equation, A * B = C can be converted into (A % 11) * (B % 11) = (C % 11) where the left-hand side of the equation is a constant value and the right-hand side will be an equation in 1 variable X which can be solved to find the value of X. There might be the possibility of X can have a negative value after performing modulo with 11, for that case consider the positive value of X.
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 replaced digit // in the product of a*b int findMissingDigit(string a, string b, string c) { // Keeps track of the sign of the // current digit int w = 1; // Stores the value of a % 11 int a_mod_11 = 0; // Find the value of a mod 11 for // large value of a as per the // derived formula for ( int i = a.size() - 1; i >= 0; i--) { a_mod_11 = (a_mod_11 + w * (a[i] - '0' )) % 11; w = w * -1; } // Stores the value of b % 11 int b_mod_11 = 0; w = 1; // Find the value of b mod 11 for // large value of a as per the // derived formula for ( int i = b.size() - 1; i >= 0; i--) { b_mod_11 = (b_mod_11 + w * (b[i] - '0' )) % 11; w = w * -1; } // Stores the value of c % 11 int c_mod_11 = 0; // Keeps track of the sign of x bool xSignIsPositive = true ; w = 1; for ( int i = c.size() - 1; i >= 0; i--) { // If the current digit is the // missing digit, then keep // the track of its sign if (c[i] == 'x' ) { xSignIsPositive = (w == 1); } else { c_mod_11 = (c_mod_11 + w * (c[i] - '0' )) % 11; } w = w * -1; } // Find the value of x using // the derived equation int x = ((a_mod_11 * b_mod_11) - c_mod_11) % 11; // Check if x has a negative sign if (!xSignIsPositive) { x = -x; } // Return positive equivalent // of x mod 11 return (x % 11 + 11) % 11; } // Driver Code int main() { string A = "123456789" ; string B = "987654321" ; string C = "12193263111x635269" ; cout << findMissingDigit(A, B, C); return 0; } |
Java
// Java program for the above approach class GFG { // Function to find the replaced digit // in the product of a*b public static int findMissingDigit(String a, String b, String c) { // Keeps track of the sign of the // current digit int w = 1 ; // Stores the value of a % 11 int a_mod_11 = 0 ; // Find the value of a mod 11 for // large value of a as per the // derived formula for ( int i = a.length() - 1 ; i >= 0 ; i--) { a_mod_11 = (a_mod_11 + w * (a.charAt(i) - '0' )) % 11 ; w = w * - 1 ; } // Stores the value of b % 11 int b_mod_11 = 0 ; w = 1 ; // Find the value of b mod 11 for // large value of a as per the // derived formula for ( int i = b.length() - 1 ; i >= 0 ; i--) { b_mod_11 = (b_mod_11 + w * (b.charAt(i) - '0' )) % 11 ; w = w * - 1 ; } // Stores the value of c % 11 int c_mod_11 = 0 ; // Keeps track of the sign of x boolean xSignIsPositive = true ; w = 1 ; for ( int i = c.length() - 1 ; i >= 0 ; i--) { // If the current digit is the // missing digit, then keep // the track of its sign if (c.charAt(i) == 'x' ) { xSignIsPositive = (w == 1 ); } else { c_mod_11 = (c_mod_11 + w * (c.charAt(i) - '0' )) % 11 ; } w = w * - 1 ; } // Find the value of x using // the derived equation int x = ((a_mod_11 * b_mod_11) - c_mod_11) % 11 ; // Check if x has a negative sign if (!xSignIsPositive) { x = -x; } // Return positive equivaluent // of x mod 11 return (x % 11 + 11 ) % 11 ; } // Driver Code public static void main(String args[]) { String A = "123456789" ; String B = "987654321" ; String C = "12193263111x635269" ; System.out.println(findMissingDigit(A, B, C)); } } // This code is contributed by saurabh_jaiswal. |
Python3
# Python3 Program to implement the above approach # Function to find the replaced digit # in the product of a*b def findMissingDigit(a, b, c): # Keeps track of the sign of the # current digit w = 1 # Stores the value of a % 11 a_mod_11 = 0 # Find the value of a mod 11 for # large value of a as per the # derived formula for i in range ( len (a) - 1 , - 1 , - 1 ): a_mod_11 = (a_mod_11 + w * ( ord (a[i]) - ord ( '0' ))) % 11 w = w * - 1 # Stores the value of b % 11 b_mod_11 = 0 w = 1 # Find the value of b mod 11 for # large value of a as per the # derived formula for i in range ( len (b) - 1 , - 1 , - 1 ): b_mod_11 = (b_mod_11 + w * ( ord (b[i]) - ord ( '0' ))) % 11 w = w * - 1 # Stores the value of c % 11 c_mod_11 = 0 # Keeps track of the sign of x xSignIsPositive = True w = 1 for i in range ( len (c) - 1 , - 1 , - 1 ): # If the current digit is the # missing digit, then keep # the track of its sign if (c[i] = = 'x' ): xSignIsPositive = (w = = 1 ) else : c_mod_11 = (c_mod_11 + w * ( ord (c[i]) - ord ( '0' ))) % 11 w = w * - 1 # Find the value of x using # the derived equation x = ((a_mod_11 * b_mod_11) - c_mod_11) % 11 # Check if x has a negative sign if ( not xSignIsPositive): x = - x # Return positive equivaluent # of x mod 11 return (x % 11 + 11 ) % 11 A = "123456789" B = "987654321" C = "12193263111x635269" print (findMissingDigit(A, B, C)) # This code is contributed by divyeshrabadiya07. |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to find the replaced digit // in the product of a*b static int findMissingDigit( string a, string b, string c) { // Keeps track of the sign of the // current digit int w = 1; // Stores the value of a % 11 int a_mod_11 = 0; // Find the value of a mod 11 for // large value of a as per the // derived formula for ( int i = a.Length - 1; i >= 0; i--) { a_mod_11 = (a_mod_11 + w * (( int )a[i] - 48)) % 11; w = w * -1; } // Stores the value of b % 11 int b_mod_11 = 0; w = 1; // Find the value of b mod 11 for // large value of a as per the // derived formula for ( int i = b.Length - 1; i >= 0; i--) { b_mod_11 = (b_mod_11 + w * (( int )b[i] - 48)) % 11; w = w * -1; } // Stores the value of c % 11 int c_mod_11 = 0; // Keeps track of the sign of x bool xSignIsPositive = true ; w = 1; for ( int i = c.Length - 1; i >= 0; i--) { // If the current digit is the // missing digit, then keep // the track of its sign if (c[i] == 'x' ) { xSignIsPositive = (w == 1); } else { c_mod_11 = (c_mod_11 + w * (( int )c[i] - '0' )) % 11; } w = w * -1; } // Find the value of x using // the derived equation int x = ((a_mod_11 * b_mod_11) - c_mod_11) % 11; // Check if x has a negative sign if (xSignIsPositive == false ) { x = -x; } // Return positive equivaluent // of x mod 11 return (x % 11 + 11) % 11; } // Driver Code public static void Main() { string A = "123456789" ; string B = "987654321" ; string C = "12193263111x635269" ; Console.Write(findMissingDigit(A, B, C)); } } // This code is contributed by ipg2016107. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the replaced digit // in the product of a*b function findMissingDigit(a, b, c) { // Keeps track of the sign of the // current digit let w = 1; // Stores the value of a % 11 let a_mod_11 = 0; // Find the value of a mod 11 for // large value of a as per the // derived formula for (let i = a.length - 1; i >= 0; i--) { a_mod_11 = (a_mod_11 + w * (a[i].charCodeAt(0) - '0' .charCodeAt(0))) % 11; w = w * -1; } // Stores the value of b % 11 let b_mod_11 = 0; w = 1; // Find the value of b mod 11 for // large value of a as per the // derived formula for (let i = b.length - 1; i >= 0; i--) { b_mod_11 = (b_mod_11 + w * (b[i].charCodeAt(0) - '0' .charCodeAt(0))) % 11; w = w * -1; } // Stores the value of c % 11 let c_mod_11 = 0; // Keeps track of the sign of x let xSignIsPositive = true ; w = 1; for (let i = c.length - 1; i >= 0; i--) { // If the current digit is the // missing digit, then keep // the track of its sign if (c[i] == 'x' ) { xSignIsPositive = (w == 1); } else { c_mod_11 = (c_mod_11 + w * (c[i].charCodeAt(0) - '0' .charCodeAt(0))) % 11; } w = w * -1; } // Find the value of x using // the derived equation let x = ((a_mod_11 * b_mod_11) - c_mod_11) % 11; // Check if x has a negative sign if (!xSignIsPositive) { x = -x; } // Return positive equivaluent // of x mod 11 return (x % 11 + 11) % 11; } // Driver Code let A = "123456789" ; let B = "987654321" ; let C = "12193263111x635269" ; document.write(findMissingDigit(A, B, C)); // This code is contributed by Potta Lokesh </script> |
2
Time Complexity: O(log10A + log10B)
Auxiliary Space: O(1)
Contact Us