Find the Missing Digit in Given Product of Large Positive Integers

Abhishek Ranjan
Last Updated: May 13, 2022

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!

 

Was this article helpful ?
1 upvote