I have a number Now if Examples:
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

Let us take the example: $n = 5,\ x = 11327$ Doing the long multiplication, we get
Now let us try to make the number $y$, (considering unit place as $1^{st}$ digit and so on)
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. answered 22 Jul '17, 22:59
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)
Nice implementation. But isn't it an overkill? Also, your code gets RE when the answer contains a '0'.
(23 Jul '17, 00:46)
1
Thanks, fixed. And yes, it is overkill :P
(23 Jul '17, 00:52)
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_21 that was tricky :D
(29 Jul '17, 02:23)

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. answered 22 Jul '17, 06:59
@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)
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)
