Problem Link : http://www.spoj.com/problems/MULTII/
Solution:
The problem is easy , once we see it as a graph . Consider a graph with vertices representing remainders (0 - (N-1) ). Initially we have only { d1%N,d2% N , .. dk%N } vertices , that can be reached . Now from each of these vertices , we can go to (10*k1 + k2)%N , where k1 is any vertex , and k2 is a digit belonging to that subset. So just do a BFS/DFS on this graph to see if vertex with remainder 0 can be reached or not !
Example : suppose we have only 7,8,9 that we can be used , and N = 11. Then from 7 we can go to
7*10+8%11 = 1 , 7*10 + 9 = 2 , 7*10 + 9 = 3, 8*10 + 7 = 10 , 8*10 + 8 = 0 . Hence we reach the state 0 .
Complexity will be O(10*N).
Solution:
The problem is easy , once we see it as a graph . Consider a graph with vertices representing remainders (0 - (N-1) ). Initially we have only { d1%N,d2% N , .. dk%N } vertices , that can be reached . Now from each of these vertices , we can go to (10*k1 + k2)%N , where k1 is any vertex , and k2 is a digit belonging to that subset. So just do a BFS/DFS on this graph to see if vertex with remainder 0 can be reached or not !
Example : suppose we have only 7,8,9 that we can be used , and N = 11. Then from 7 we can go to
7*10+8%11 = 1 , 7*10 + 9 = 2 , 7*10 + 9 = 3, 8*10 + 7 = 10 , 8*10 + 8 = 0 . Hence we reach the state 0 .
Complexity will be O(10*N).
