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.
@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?
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)
Since 1^{st} digit of x is 7, 1^{st} digit of y should be 3 (7 * 3 = 1 \mod 10), \ \therefore y = 3
Now we have 1 as the 1^{st} digit of product and want (n-1) zeroes (0's) after it.
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'.
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 \times n \times \log_{10}(x \times answer)) time. Refer to @meooow 's comment for the time complexity.
Here is the code for the above algorithm in Python 3.
The complexity is actually \mathcal{O}(10 \times n \times \log_{10}(x \times 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
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 \times \log_{10}(x)) = \mathcal{O}(10^8), which will be within bounds.
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.
@jennifer_21 that was tricky
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.
