You are not logged in. Please login at www.codechef.com to post your questions!

×

Find the appropriate product

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.

asked 22 Jul '17, 02:57

jennifer_21's gravatar image

0★jennifer_21
195
accept rate: 0%

edited 22 Jul '17, 03:07


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$), $\ \therefore 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 \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.

https://ideone.com/LqKmI7

link

answered 22 Jul '17, 22:59

c_utkarsh's gravatar image

5★c_utkarsh
1.1k5
accept rate: 17%

edited 23 Jul '17, 00:50

2

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 :D

(23 Jul '17, 00:10) meooow ♦6★

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

(23 Jul '17, 00:46) c_utkarsh5★
1

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

(23 Jul '17, 00:52) meooow ♦6★
1

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.

(28 Jul '17, 04:48) jennifer_210★

@jennifer_21 that was tricky :D
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.

(29 Jul '17, 02:23) meooow ♦6★

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.

link

answered 22 Jul '17, 06:59

liaojh's gravatar image

5★liaojh
1825
accept rate: 7%

@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?

(22 Jul '17, 15:20) jennifer_210★
1

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.

(23 Jul '17, 15:42) liaojh5★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,736
×639

question asked: 22 Jul '17, 02:57

question was seen: 403 times

last updated: 29 Jul '17, 02:30