Smallest multiple with constraints

smwc.py

"""
Problem statement:
------------------
Given a number 'n', design an algorithm that will output the smallest
integer number 'X' which contains only the digits {0, 1} such that
X mod n = 0 and X > 0
(1 <= n <= 100000)
"""
def solve(n):
	if n < 2:
		return 1
	# dp[j] stores the smallest quotient 'x' that:
	# [1] Leaves remainder 'j',
	# [2] Perfectly divide 'n', and
	# [3] Has only digits {0, 1}
	dp = [0] * n
	i = 0

	while dp[0] == 0:
		x = pow(10, i)
		xmodn = x % n		
		if xmodn == 0:
			return x
		# 'dp1' is the table that stores the *next* state for the subset sum
		# that we'll compute to store the quotient after dividing by some 'x'
		# that has only digits {0, 1}
		dp1 = [0] * n
		dp1[xmodn] = x
		for j in range (n-1, -1, -1):
			dp1[j] = (dp[(j - xmodn) % n] + x) if dp[(j - xmodn) % n] != 0 else dp1[j]

		# We then merge 'dp' and 'dp1' so that the smallest value of the
		# quotient for a given remainder is retained
		for j in range(0, n):
			dp[j] = dp1[j] if dp[j] == 0 else dp[j]
		i = i + 1
	
	return dp[0]

for n in range (1, 100):
	sn = solve(n)
	print "solve(%d): %d" % (n, solve(n))
	if sn % n != 0:
		print "Remainder is %d not 0" % (sn % n)

print solve(99998)