To design an algorithm that will output the smallest integer number 'x' which contains only digits 1's and 0's such that x mod n = 0 and x > 0..... For example:
2 divides 10
3 divides 111
4 divides 100
5 divides 10
6 divides 1110
7 divides 1001 and so on.
The 1's and 0's are in base 10 representation.
I know that we can solve this using the pigeon hole principle but in this problem we are interested in the smallest number.
I was thinking of using a DP approach similar to a subset sum problem where the set contains 1, 10, 100, 1000 and so on. I am not completely clear about how to formulate the recurrence relation for this problem. Can someone give some insight?