Dados dos enteros grandes en forma de strings A y B y su producto también en forma de string C tal que un dígito del producto se reemplaza con X , la tarea es encontrar el dígito reemplazado en el producto C.
Ejemplos:
Entrada: A = 51840, B = 273581, C = 1418243×040
Salida: 9
Explicación:
El producto de los enteros A y B es 51840 * 273581 = 14182439040. Al compararlo con C, se puede concluir que el dígito reemplazado fue 9 Por lo tanto, imprima 9.Entrada: A = 123456789, B = 987654321, C = 12193263111 × 635269
Salida: 2
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es encontrar el producto de dos números enteros grandes A y B usando el enfoque discutido en este artículo y luego comparándolo con C para encontrar el dígito X faltante resultante .
Complejidad de tiempo: O((log 10 A)*(log 10 B))
Espacio auxiliar: O(log 10 A + log 10 B)
Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso de las siguientes observaciones:
Supongamos que N es un número entero tal que N = a m a m-1 a m-2 …….a 2 a 1 a 0 donde a x representa el dígito x . Ahora, N se puede representar como:
=> N = a m * 10 m + a m-1 * 10 m-1 + ………… + a 1 * 10 + a 0Realizando la operación de módulo con 11 en la ecuación anterior:
=> N (mod 11) = a m * 10 m + a m-1 * 10 m-1 + ………… + a 1 * 10 + a 0 (mod 11)
=> N (mod 11)= a m (-1) m + a m-1 (-1) m-1 + ……….. + a 1 (-1) + a 0 (mod 11) [Ya que 10 ≡ -1 (mod 11)]
=> N (mod 11) = T (mod 11) donde T = a 0 –a 1 + a 2 …… + (-1) m a m
Por lo tanto, de la ecuación anterior, A * B = C se puede convertir en (A % 11) * (B % 11) = (C % 11) donde el lado izquierdo de la ecuación es un valor constante y el lado derecho El lado de la mano será una ecuación en 1 variable X que se puede resolver para encontrar el valor de X. Puede existir la posibilidad de que X pueda tener un valor negativo después de realizar el módulo con 11 , para ese caso considere el valor positivo de X.
A continuación se muestra la implementación del enfoque anterior:
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 equivaluent // 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
Complejidad de Tiempo: O(log 10 A + log 10 B)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por sourashis69 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA