Find the Missing Digit in Given Product of Large Positive Integers

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)}.......d₁d₀ be the decimal representation of N.

So, N = d_{(m - 1)} * 10^(m-1) + d_{(m - 2)} * 10^{(m- 2)} +.......+d₁ * 10¹ + d₀ * 10⁰. 

taking mod with 11,

N%11 = (d_{(m - 1)} * 10^(m-1) + d_{(m - 2)} * 10^{(m- 2)} +.......+d₁ * 10 + d₀)%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)} + ........... - d₁ + d₀

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 * -1ⁱ + ........... - r₁ + r₀

So if we shift all the terms of C to the left-hand side except X * -1ⁱ, 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 P, Q, and R is log10P, log10Q, 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. 
Check out this problem - First Missing Positive 

To learn more about such data structures and algorithms, Coding Ninjas Studio 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!