Smallest Multiple With Only Digits 0 and 1 (BFS on remainders)

Finally, Rafid is curious: what's the smallest multiple of a number N whose digits are only 0s and 1s? He wants an efficient way to find it, not brute-force checking multiples one by one. Given N, find the smallest positive multiple of N that consists only of the digits 0 and 1 (e.g. for N=3, answer is 111). Model this as a shortest-path/BFS problem over the N possible remainders mod N, since brute-force checking multiples directly is infeasible for large N.

3

111