Rafael Sofi-Zadeh - 1 year ago 59
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.

``````def digitsum(n):