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

Solution 1

got the answer now :)

int count=1, rem=1; 
while(rem)
{
 rem= (rem*10+1)%n; count++;
} 
 while(count--){ cout<<"1";}

Solution 2

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.

Comments

[Aravind]

you just said the multiple could exceed integer range.

[twalberg]

@HighPerformanceMark The question does not exclude integers or long integers - it merely states that a solution may exceed the range of such. It excludes using complex data structures. It does not exclude using modular arithmetic and observations of the relation between x mod 3 and (x*10+1) mod 3 to calculate a string of characters that represent an appropriate multiple without actually calculating such multiple...

[Euler]

@Aravind yes it is count is the no of times 1 is occuring in the multiple while loop is printing that number

[akaHuman]

It's a beautiful solution! Could you please elaborate a little on how it uses modular arithmetic?

[greybeard]

Using long long to evade to exceed the range of int, long is poor. Did you try to understand how other solutions don't need numbers (much) greater than the number given?

[Pranav Nandan]

I do think this is the actual solution not others. But just wanted to understand how is it efficient than trying 1,11,111 etc ? We are calculating 10^k mod A (assume A=9(10x+3)) every iteration, with increasing k, right? What if the variable storing 10^k overflows and the result is very big? Is this the optimum method interviewer expects using congruent properties? -Thanks.. I'm just curious.

[mcdowella]

The arithmetic required is mod 9(10x + 3) and if this overflows you are out of luck unless you switch to multiple precision, but that happens some time after 10^k overflows. The efficiency follows from the fact that the baby-step/giant-step algorithm allows you to search a range of N possibilities in time O(sqrt(N))

[amdev]

I think it's not a good answer for a job interview or homework. Use Fermat's little theorem is the way to go.

[albanx]

as @akaHuman is commenting some code must does not says to much why this is the best solution