Numbers ending in 3 have at least one multiple having all ones

Question

Hi Here is a Q that was asked in Adobe Interview.

Numbers ending in 3 have at least one multiple having all ones. 
for eg., 3 and 13 have amultiples like 111 and 111111 respectively. Given such 
a no. , find the smallest such multiple of that number. The multiple can 
exceed the range of int, long. You cannot use any complex data structure.

Can you provide me with an efficient solution

Answer 1

Here is an attempt to do it more efficiently that trying 1, 11, 111, 111.. Could this pay off. Is there a more elegant answer better than trying numbers one at a time?

Write the numbers 1, 11, 111, ... as (10^k - 1) / 9, where the division is known to be exact. Given a target number in the form 10x+3 we want to find the smallest k solving (10^k - 1) / 9 = Y(10x + 3) where Y is an integer. Look for small solutions of 10^k = 1 mod 9(10x + 3). This is http://en.wikipedia.org/wiki/Discrete_logarithm except that arithmetic mod 9(10x + 3) does not necessarily form a group - however the http://en.wikipedia.org/wiki/Baby-step_giant-step algorithm should still apply and could be used to search steadily increasing ranges of k, instead of searching possible values of k one at a time.