isn't it just dp? suppose dp[i] denotes the minimum number such that the sum of cubes of its digits is i. Then, dp[n]=min(add a digit 9 to left of dp[n-729], add a digit 8 to left of dp[n-512],...,add digit 1 to left of dp[n-1]). This, of course, requires some edge cases. eg. dp[1]=1(base case 1). dp[2]=min(add 1 to left of dp[1])=11. It needs 9*n operations so it is O(n).