How can I find a number whose sum of digits' cube is equal to n
Let us consider the more general problem in which we fix integers $0 &lt; a_1 &lt; \cdots &lt; a_m$, and then given a positive integer $n$, we want to determine the smallest non-negative integer combination $\sum_{i=1}^m d_i a_i$ which is equal to $n$, if any exists, or determine the none exists. Here one combination $(d_1,\ldots,d_m)$ is smaller than another $(e_1,\ldots,e_m)$ if either $d_1+\cdots+d_m &lt; e_1+\cdots+e_m$, or $d_1+\cdots+d_m = e_1+\cdots+e_m$ and for some $i$ we have $d_1=e_1,\ldots,d_{i-1}=e_{i-1}$ and $d_i &gt; e_i$.

The main observation is that any optimal solution satisfies $d_i &lt; a_m$ for all $i &lt; m$. Indeed, if $d_i \geq a_m$ then we can decrease $d_i$ by $a_m$ and increase $d_m$ by $a_i$ to obtain a better solution. (In fact, this shows that $d_i &lt; \mathrm{lcm}(a_i,a_m)/a_i$.) This suggests the following algorithm:


  Go over all possible values of $d_1,\ldots,d_{m-1}$ such that $0 \leq d_1,\ldots,d_{m-1} &lt; a_m$. For each such setting, check whether it can be completed to a solution, that is, whether $a_m$ divides $n-\sum_{i=1}^{m-1} d_i a_i$. Choose the smallest solution, if any exists.


This algorithm runs in time $O(\log n)$, where the hidden constant depends in some horrible way on $a_1,\ldots,a_m$. This is optimal (up to the value of the hidden constant) since clearly we need to read the entire input.



The algorithm above doesn't really help you solve your case in practice, since the hidden constant is too large. Presumably you were supposed to use dynamic programming, an algorithm which runs in time $O(n)$ and finds the minimal length of a solution (perhaps it can also be tweaked to find a solution of minimal value).