algorithm - How to calculate smallest multiple formed only of the digit 1? -

i given number k in range 1 10000. problem find smallest multiple can written digit 1 (known repunit). k=3 solution 111 because 3 divides 111, 3 not divide 1 or 11. k=7, solution 111111 (six ones).

how calculate solution k?

i understand need use remainders since solution can big (or suppose use biginteger class)

if you're guaranteed solution (at least n , multiples of 5, there no solution. haven't given thought others, think rest should have solution):

(a + b) % c = ((a % c) + (b % c)) % c (a * b) % c = ((a % c) * (b % c)) % c 

where % modulo operator: a % b = remainder of division of b. means can take modulos between additions , multiplications, solve problem.

using this, can use following algorithm, linear in number of digits of result , uses o(1) memory:

number_of_ones = 1 remainder = 1 % n while remainder != 0:   ++number_of_ones    # here add 1 result,   # store result's value mod n.   # when 0, our solution.   remainder = (remainder * 10 + 1) % n  print 1 number_of_ones times 

followup question: if can use 0 , 1?