import collections
class Solution:
# @param A : integer
# @return a strings
def multiple(self, A):
queue = collections.deque([1])
result = '0'
dest = None
parents = {1: None}
while queue:
current = queue.popleft()
if current % A == 0:
dest = current
break
val1 = (current * 10) % A
if val1 not in parents:
parents[val1] = -current
queue.append(val1)
val2 = (val1 + 1) % A
if val2 not in parents:
parents[val2] = current
queue.append(val2)
# print(parents_0, parents_1)
if dest is not None:
tmp = []
while dest is not None:
dest = parents[dest]
if dest and dest < 0:
dest = -dest
item = '0'
else:
item = '1'
tmp.append(item)
result = ''.join(reversed(tmp))
return result
