erriio's blog

How can I solve this problem?
By erriio, history, 4 years ago, In English

Sum of cubes Please,help.

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

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).

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Code?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +13 Vote: I do not like it

      Why do you need a code? I believe that the logic is good enough. I think the code to this would be short and easy. You should give it a try yourself. Or maybe you can ask if you are having a problem somewhere in your own code. Asking for help is one thing and just relying on others is another thing. Please try to understand. I am not discouraging you from asking though.

      → Reply