Найдите недостающую цифру в заданном произведении больших натуральных чисел

Даны два больших целых числа в виде строк A и B и их произведение также в виде строки C , такое что одна цифра произведения заменена на X , задача состоит в том, чтобы найти замененную цифру в произведении C.

Примеры:

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

Наивный подход: самый простой подход к решению данной проблемы — найти произведение двух больших целых чисел A и B, используя подход, обсуждаемый в этой статье, а затем сравнить его с C, чтобы найти результирующую пропущенную цифру X.

Временная сложность: O((log ₁₀ A)*(log ₁₀ B))
Вспомогательное пространство: O (log ₁₀ A + log ₁₀ B)

Эффективный подход. Описанный выше подход также можно оптимизировать, используя следующие наблюдения:

Suppose N is an integer such that N = a_ma_m-1a_m-2 …….a₂a₁a₀ where a_x represents the x^th digit. Now, N can be represented as:
=> N = a_m * 10^m + a_m-1 * 10^m-1 + ………… + a₁ * 10 + a₀

Performing the modulo operation with 11 in the above equation:

=> N (mod 11) = a_m * 10^m + a_m-1 * 10^m-1 + ………… + a₁ * 10 + a₀ (mod 11)
=> N (mod 11) = a_m(-1)^m + a_m-1(-1)^m-1 + ……….. + a₁(-1) + a₀   (mod 11)   [Since 10 ≡ -1 (mod 11)]
=> N (mod 11) = T (mod 11) where T = a₀ – a₁ + a₂ …… + (-1)^ma_m

Следовательно, из приведенного выше уравнения A * B = C можно преобразовать в (A % 11) * (B % 11) = (C % 11) , где левая часть уравнения представляет собой постоянное значение, а правая — стороны будет уравнение с 1 переменной X , которое можно решить, чтобы найти значение X . Может быть вероятность того, что X может иметь отрицательное значение после выполнения по модулю с 11 , для этого случая рассмотрим положительное значение X .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O (log ₁₀ A + log ₁₀ B)
Вспомогательное пространство: O(1)