I got solutions on internet but it is quite difficult to understand. Plz can someone explain this.
You are given an integer N. You have to find smallest multiple of N which consists of digits 0 and 1 only. Since this multiple could be large, return it in form of a string.
Note: - Returned string should not contain leading zeroes.
For N = 55, 110 is smallest multiple consisting of digits 0 and 1. For N = 2, 10 is the answer.
It is a quite well known problem that can be solved using BFS in O(N). You can find a similar problem here : http://www.spoj.com/problems/ONEZERO/
Your state is your current number so far modulo N. At each step you move to (state*10 + 0) % n, and (state*10 + 1) % n. You are basically constructing your numbers on the go. ( Trace and see why it works). Since you execute BFS by always putting zeros first, you only care about the first time you reach a certain modulo.
Once you reach state 0, you just print the path.