TooNewbie's blog

By TooNewbie, 8 years ago, In English

Help me to solve this problem : Find minimal k which sum of k's digit's square equals to N where N<=5000. For example: if N=100 then k=68 || if N=345 then k=277999.

Note: I think this problem is DP, but i couldn't do it.

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think you can make the dp D[i] = { (n, a1, a2, ... , a9) | n <= N }, a list of all the numbers that can be generated with the digits from 1 to i, with the digits they need (for your sample D[9] will contain (345, 0, 1, 0, 0, 0, 0, 2, 0, 3) ) So for each number i from 1 to 10 you have a list of all possible n you can obtain with numbers from 1 to i. We have D[0] = { (0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } For passing from D[i] to D[i + 1], we first set D[i + 1] = D[i], and for each element in D[i + 1] (each pair of 10 numbers), we verify if by adding digit i + 1 we can create a new number, or optimize an existing one.

struct d
{
    int frequence[10]; /// the number of times a digit is neded
    int n;   /// the value of the number obtained with the digits
}

vector <d> DP[10];
DP[0].push_back({ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 });

for (int i = 1; i <= 9; ++i) {
    DP[i] = DP[i - 1];
    for (auto j : DP[i]) {
        /* 
        if by adding the digit i to the number j (so the new value will be j.n + i * i) we obtain a number we do not have who is smaller than N (we don't need the ones bigger), we insert it to DP[i]
        if j.n + i * i is already in DP[i], but the number of needed digits (the sum of frequence[k]) is bigger to the sum of j.freqence[k] + 1, we replace it. If it is equal, we verify in O(10) the better
        */
    }
}

/// now we just have to iterate in DP[9] to see if we have found N.
/// complexity: O(N * 10 * 10)

this works because: — it will calculate all possible numbers — it will only keep the ones with less digits — it will always try to minimise digits

»
8 years ago, # |
Rev. 3   Vote: I like it +10 Vote: I do not like it

You can solve it with DP by making DP[d][s] = is it possible to make a sum of s with a number of d digits?. The first step is to find the minimum digits that can lead to N. After that, you can perform greedily, assigning the smallest possible digit at each step. I attach code.

C++ Code
»
8 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Let's denote dp[i] as the minimum number, which sum of digits' square is i. We can keep it as a string or a BigIntger, which length doesn't exceed 100 (ez to prove).

dp[0] = 0; others are infinity. Consider we are at dp[i]. Now let's iterate over the digits, we will add to the current, say j. Then we update dp[i + j * j] = min(dp[i + j * j], dp[i] * 10 + j)

The answer is dp[N].