SPOJ.com - Problem ONEZERO

SPOJ.com - Problem ONEZERO
Certain positive integers have their decimal representation consisting only of ones and zeros, and having at least one digit one, e.g. 101. If a positive integer does not have such a property, one can try to multiply it by some positive integer to find out whether the product has this property.

Input

Number K of test cases (K is approximately 1000);
in each of the next K lines there is one integer n (1 <= n <= 20000)

Output

For each test case, your program should compute the smallest multiple of the number n consisting only of digits 1 and 0 (beginning with 1).

Suppose the number that you want is X. X mod N = 0.

So you need to store only N states i.e. 0 to n-1. Start with 1.

Implement bfs approach. If the current state modulo is Y, append 0 to it i.e calculate Y*10 + 0 and find its modulo which will lead you to a new modulo state.

Similary append 1 to Y. i.e calculate Y*10 + 1 and find its modulo.

Example: if Y=11 append 0 to it to get 110 and append 1 to Y to get 111.

Have a parent array which will store the previous modulo state from which the current modulo state is reached. This parent array also acts as checkpoint to check if a modulo state is already visited or not.

Have a value array to store the value (1 or 0) that is appended to the parent modulo state to get the current modulo state.

Once the modulo state 0 is reached stop bfs and backtrack using parent array and value array to get the number (i.e smallest multiple of the number n consisting only of digits 1 and 0 beginning with 1).

Read full article from SPOJ.com - Problem ONEZERO