# Find the Missing Digit in Given Product of Large Positive Integers

## Problem Statement

You are given three non-negative integers, PQ, and R, in the form of a string. R is the product of P and Q. One of the digits of R has been replaced with X. Your task is to find X.

Constraints

``1 <= |P|, |Q|, |R| <= 5e5``

## Sample Test Cases

``````Input: 89568956
788966631
70666917457X07236
Output: 5

Explanation: 89568956 x 788966631 = 70666917457507236
The 12th digit from the left is missing in the number, so x = 5
``````
``````Input: 89568956
788966631
706669174575X7236
Output: 0
Explanation: 89568956 x 788966631 = 70666917457507236
The 13th digit from the left is missing in the number, so x = 0``````

## Approach

Let N be a non-negative integer and m be the number of digits in the decimal representation of N. Let d(m-1)d(m - 2).......d1d0 be the decimal representation of N.

So, N = d(m - 1) * 10(m-1) + d(m - 2) * 10(m- 2) +.......+d1 * 101 + d0 * 100

taking mod with 11,

N%11 = (d(m - 1) * 10(m-1) + d(m - 2) * 10(m- 2) +.......+d1 * 10 + d0)%11

-1 mod 11 = (-1 + 11)mod11 = 10mod11

Using above equation,

So, N%11 = d(m - 1) * -1(m - 1) + d(m - 2) * -1(m - 2) + ........... - d1 + d0

We can use the above equation to find X.

Given, P * Q = R

taking mod with 11,

(P * Q) mod 11 = R mod 11

(P mod 11) * (Q mod 11) = (R mod 11)

The left-hand side (P mod 11) * (Q mod 11) is a constant, and on the right-hand side, X is unknown.

R%11 = r(m - 1) * -1(m - 1) + r(m - 2) * -1(m - 2) +..........+ X * -1i + ........... - r1 + r0

So if we shift all the terms of C to the left-hand side except X * -1i, we can get the value of X. If X is at an odd place, we will multiply it with -1.

## Code

``````#include <bits/stdc++.h>
using namespace std;
int main(){
string P, Q, R;
cin >> P >> Q >> R;
//size of P
int m = P.size();
//to store P mod 11
int Pmod11 = 0;
//keep the track of sign of current digit
int sign = 1;
//calculate the value of P mod 11 using the equation 1
for(int i = m - 1; i >= 0; --i){
Pmod11 = Pmod11 + sign * (P[i] - '0');
Pmod11 = Pmod11%11;
//change the sign
sign = -sign;
}
//size of Q
m = Q.size();
//to store Q mod 11
int Qmod11 = 0;
//keep the track of sign of current digit
sign = 1;
//calculate the value of P mod 11 using the equation 1
for(int i = m - 1; i >= 0; --i){
Qmod11 = Qmod11 + sign * (Q[i] - '0');
Qmod11 = Qmod11%11;
//change the sign
sign = -sign;
}
//size of R
m = R.size();
//to store (Q mod 11 - X * sign of X)
int Rmod11 = 0;
//keep the track of sign of current digit
sign = 1;
//keep the track of sign of X
int signofX = 1;
for(int i = m - 1; i >= 0; --i){
if(R[i] != 'X'){
Rmod11 = Rmod11 + sign * (R[i] - '0');
Rmod11 = Rmod11%11;
}
else{
//store the sign of X
signofX = sign;
}
//change the sign
sign = -sign;
}
//find value of X by shifting all the terms of R to LHS expect X
int X = (Pmod11 * Qmod11 - Rmod11 + 11)%11;
//signofX is negative
if(signofX == -1)
X = (-X + 11)%11;
cout << X << "\n";
}``````

### Input

``````89568956
788966631
70666917457X07236``````

### Output

``5``

## Complexity

### Time Complexity

The time complexity is O(log10P + log10Q + log10R).

### Space Complexity

The space complexity is O(1).

## FAQs

1. How -1 mod 11 == 10 mod 11??
According to modulo arithmetic,
(x - y)%mod = (x%mod - y%mod + mod)%mod
The extra mod is added to keep the result positive.
by using this formula,
-1%11 = (0 - 1)%11
= (0%11 - 1%11 + 11)%11
= (11 - 1)%11
= 10%11
So, -1%11 = 10

2. Why the time complexity is O(log10P + log10Q + log10R)??
The number of digits in the base 10 representation of an integer N is log10N. So the length of the given strings PQ, and R is log10Plog10Q, and log10R, respectively. We are iterating each string once, so the time complexity is O(log10P + log10Q + log10R).

## Key Takeaways

In this article, we solved a number theory problem using modulo arithmetic. If you are practicing competitive programming or preparing for coding interviews, then number theory is one of the most important topics. Check out this library to get a better hold on it.

To learn more about such data structures and algorithms, Codestudio is a one-stop destination. This platform will help you to improve your coding techniques and give you an overview of interview experiences in various product-based companies by providing Online Mock Test Series and many more benefits.

Happy learning! 