minimal positive number divisible to N

Question

1<=N<=1000

How to find the minimal positive number, that is divisible by N, and its digit sum should be equal to N.

For example:
N:Result
1:1
10:190

And the algorithm shouldn't take more than 2 seconds.

Any ideas(Pseudocode,pascal,c++ or java) ?

Answer 1

Let f(len, sum, mod) be a bool, meaning we can build a number(maybe with leading zeros), that has length len+1, sum of digits equal to sum and gives mod when diving by n.

Then f(len, sum, mod) = or (f(len-1, sum-i, mod- i*10^len), for i from 0 to 9). Then you can find minimal l, that f(l, n, n) is true. After that just find first digit, then second and so on.

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, N) FOR(i, 0, N)

#define FILL(a,v) memset(a,v,sizeof(a))



const int maxlen = 120;
const int maxn = 1000;

int st[maxlen];
int n;

bool can[maxlen][maxn+1][maxn+1];
bool was[maxlen][maxn+1][maxn+1];

bool f(int l, int s, int m)
{
    m = m%n;
    if(m<0)
        m += n;

    if(s == 0)
        return (m == 0);
    if(s<0)
        return false;
    if(l<0)
        return false;   

    if(was[l][s][m])
        return can[l][s][m];

    was[l][s][m] = true;
    can[l][s][m] = false;

    REP(i,10)
        if(f(l-1, s-i, m - st[l]*i))
        {
            can[l][s][m] = true;
            return true;
        }
    return false;
}


string build(int l, int s, int m)
{
    if(l<0)
        return "";
    m = m%n;
    if(m<0)
        m += n;
    REP(i,10)
        if(f(l-1, s-i, m - st[l]*i))
        {
            return char('0'+i) + build(l-1, s-i, m - st[l]*i);
        }
    return "";
}

int main(int argc, char** argv)
{
    ios_base::sync_with_stdio(false);

    cin>>n;
    FILL(was, false);   
    st[0] = 1;
    FOR(i, 1, maxlen)
        st[i] = (st[i-1]*10)%n;
    int l = -1;
    REP(i, maxlen)
        if(f(i, n, n))
        {
            cout<<build(i,n,n)<<endl;
            break;
        }

    return 0;
}

NOTE that this uses ~250 mb of memory.

EDIT: I found a test where this solution runs, a bit too long. 999, takes almost 5s.