Smallest multiple with constraints

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)

Problem credits: Ayush on the Stony Brook Puzzle Society Facebook Group

Insight: Suppose n = 6. Consider some numerator (target answer X) to be 1101. Can this be correct? We can verify by dividing and checking the remainder. 1101 mod 6 = 3, so we've overshot the answer by 3 or more (since we might not have the smallest X).

Another way to get the same remainder '3' is to say:

• 1000 mod 6 = 4
• 100 mod 6 = 4
• 00 mod 6 = 0
• 1 mod 6 = 1

Add up all the remainders and take that mod 6. Hence, (4 + 4 + 0 + 1) mod 6 = 9 mod 6 = 3.

Which basically means that we want to find that subset of powers of 10, added together (mod n) leave a remainder of 0. We can solve this using dynamic programming using a technique similar to the one used to solve the subset sum problem. The solution to our problem (and to the subset sum problem) is pseudo-polynomial. Specifically, our problem is solved in time O(n log X).

Here is the ideone link, and below is the code (in python) to solve it.

	"""
	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)

view raw smwc.py hosted with ❤ by GitHub

Follow up problem:

Find a number 'X' given an 'n' (similar to the problem above) except that you are allowed to only use digits {0, 3, 5, 8}. Can you always find a solution for any 'n'?