SPOJ - INUMBER (Can't seem to develop a soluti

Question

I'm trying to solve this problem on SPOJ INUMBER.

Problem statement is as follows:

For the given number n find the minimal positive integer divisable by n, with the sum of digits equal to n.

INPUT

t – the number of test cases, then t test cases follow. (t <= 50)
Test case description:
n - integer such that 0 < n <= 1000

OUTPUT

For each test case output the required number (without leading zeros).

EXAMPLE:

Input:
2
1
10

Output:
1
190

I can only think of a brute force solution emulating the number digit by digit from 0-9 and forming a dfs structure and repeatedly checking whether it's divisible by n or not.

Before asking my question here, I did a meticulous search on this problem on the internet and couldn't found any detailed explanation. Most of them were undocumented raw code and others were giving just a jist of the solution.
I'm really interested in solving this problem not just for the points but to learn something new.

Thanks for the help Stackoverflow community :)

Answer 1

You can use a breadth first search.

Let num(p, q) be the minimum number of digits with digit sum p and remainder mod n equal to q.

We want to find num(n, 0). Then, we can greedily build the smallest such number.

We start from the state (0, 0). From a state (x, y) you can get to a state:

(x + j, (y * 10 + j) % n) 

for each digit j.

Keep track of each digit j you add and then backtrack from (n, 0) to (0, 0).

There are some implementation details to figure out. If you get stuck, I have found some implementations online: on topcoder and on github.