Rafael Sofi-Zadeh Rafael Sofi-Zadeh - 27 days ago 7
C++ Question

Find the smallest integer whose sum of squares of digits add to the given number

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.

Answer

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]