Rafael Sofi-Zadeh - 1 year ago 59

C++ Question

**Example:**

Input: | Output:

- 5 –> 12 (1^2 + 2^2 = 5)
- 500 -> 18888999 (1^2 + 8^2 + 8^2 + 8^2 + 9^2 + 9^2 + 9^2 = 500)

I have written a pretty simple brute-force solution, but it has big performance problems:

`#include <iostream>`

using namespace std;

int main() {

int n;

bool found = true;

unsigned long int sum = 0;

cin >> n;

int i = 0;

while (found) {

++i;

if (n == 0) { //The code below doesn't work if n = 0, so we assign value to sum right away (in case n = 0)

sum = 0;

break;

}

int j = i;

while (j != 0) { //After each iteration, j's last digit gets stripped away (j /= 10), so we want to stop right when j becomes 0

sum += (j % 10) * (j % 10); //After each iteration, sum gets increased by *(last digit of j)^2*. (j % 10) gets the last digit of j

j /= 10;

}

if (sum == n) { //If we meet our problem's requirements, so that sum of j's each digit squared is equal to the given number n, loop breaks and we get our result

break;

}

sum = 0; //Otherwise, sum gets nullified and the loops starts over

}

cout << i;

return 0;

}

I am looking for a fast solution to the problem.

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

Use dynamic programming. If we knew the first digit of the optimal solution, then the rest would be an optimal solution for the remainder of the sum. As a result, we can guess the first digit and use a cached computation for smaller targets to get the optimum.

```
def digitsum(n):
best = [0]
for i in range(1, n+1):
best.append(min(int(str(d) + str(best[i - d**2]).strip('0'))
for d in range(1, 10)
if i >= d**2))
return best[n]
```