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.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
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.
Name |
---|
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.
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
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.
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].