Find the appropriate product

help
number-theory

#1

I have a number n and an integer x which ends on 1, 3, 7 or 9, meaning that the last digit (rightmost digit) of x is one of those 4 numbers.

Now if z = x * y, what number do I have to choose for y such that the n last (rightmost) digits of z are equal to 1 (I mean the numerical value of the rightmost n digits of z has to be 1) while ignoring leading zeros.

Examples:

// computes y
long computeY(int n, long x) {
    // ...magic...
    return y;
}

computeY(1, 9) == 9 (because 9*9 = 81, take the n rightmost digits, result is 1)

computeY(1, 7) == 3 (because 7*3 = 21, take the n rightmost digits, result is 1)

computeY(2, 11) == 91 (because 11*91 = 1001, take the n rightmost digits, result is 1, ignore leading zeros)

computeY(3, 17) == 353 (because 353*17 = 6001, take the n rightmost digits, result is 1, ignore leading zeros)

computeY(5, 11327) == 23263 (because 11327*23263 = 263500001, take the n rightmost digits, result is 1, ignore leading zeros)

I encountered this problem during a contest at my school and am stuck, It looks like I have to use number theory but I just don’t know where to start.


#2

What are the constraints? I can think of a brute force O(n*digits in x) solution, but I definitely think there are optimizations to it.

If you want the brute force, it’s just a simulation of long multiplication.


#3

Let us take the example: n = 5,\ x = 11327

Doing the long multiplication, we get

        1 1 3 2 7  (X)
      x 2 3 2 6 3  (Y)
-----------------
        3 3 9 8 1  (line 1)
      6 7 9 6 2 x  (line 2)
    2 2 6 5 4 x x  (line 3)
  3 3 9 8 1 x x x  (line 4)
2 2 6 5 4 x x x x  (line 5)
-----------------
2 6 3 5 0 0 0 0 1

Now let us try to make the number y, (considering unit place as 1^{st} digit and so on)

  1. Since 1^{st} digit of x is 7, 1^{st} digit of y should be 3 (7 * 3 = 1 \mod 10), \ herefore y = 3
  2. Now we have 1 as the 1^{st} digit of product and want (n-1) zeroes (0's) after it.
  3. Iterate from 0 to 9 as the next digit of y and check whether it adds a 0 to the product (x * y'). If it does, update y =y'.
  4. Repeat step 3, (n-1) times, so that there are (n-1) zeroes 0's after 1 in the product.

Assuming multiplication to be an \mathcal{O}(1) operation, this algorithm takes \mathcal{O}(10 imes n imes \log_{10}(x imes answer)) time. Refer to @meooow 's comment for the time complexity.

Here is the code for the above algorithm in Python 3.

https://ideone.com/LqKmI7


#4

@liaojh The constraints are 1 \leq n \leq 18 and 1 \leq x \leq 10^n -1. Could you explain the brute force approach you mentioned? What do you mean by simulation of long multiplication? Where can I learn more about this?


#5

The complexity is actually \mathcal{O}(10 imes n imes \log_{10}(x imes answer)) because you are converting the product to string in each iteration. This can be avoided using math operations to find the ith digit, and using a table that maps digits can further decrease the complexity to just \mathcal{O}(n). This is hardly necessary since n is at most 18, but just for its own sake here is the modified code :smiley:


#6

Nice implementation. But isn’t it an overkill? Also, your code gets RE when the answer contains a ‘0’.


#7

Thanks, fixed. And yes, it is overkill :stuck_out_tongue:


#8

I thought n and x would have a much bigger constraint. c_utkarsh got here before me :D. His example offers a good idea of what my brute force solution would look like; it follows up the idea of Big Integer Arithmetic (which is really just simulation of elementary school long multiplication and more). Like meooow said, we can map out the digits to optimize. If 1 \leq n \leq 1000 and 1 \leq x \leq 10^{1000}, then the brute force will take \mathcal{O}(n imes \log_{10}(x)) = \mathcal{O}(10^8), which will be within bounds.


#9

This problem can be solved by applying the extended euclidian algorithm, the number you are brute forcing is the inverse which ext euclid (when applied correctly) returns.


#10

@jennifer_21 that was tricky :smiley:
Yes, it can indeed be solved by the extended Euclidean algorithm in time \mathcal{O}(n), but the digit-wise approach is also guaranteed to work in \mathcal{O}(n) and it is more generally applicable, since you can use it when you need some other number in last n digits instead of 1.