gol_alu's blog

help!!
By gol_alu, history, 7 years ago, In English

Is it possible to find the sum of digit in a ^ b without using Big Int? Where 0 <= a <= 9 & 1<= b <= 4000

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

Hint: let dp[i][j] = how many digits which equals to i is in your number after j multiplications.

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

    Unfortunately, I don't think that is sufficient. For example, your dp takes 128 and 821 to be the same thing, so it doesn't know how to calculate the next state. If you multiply by 2, you can get 256 and 1642 respectively, which are very different numbers.

    However, overall, I think there is a problem with the question gol_alu has asked. The most natural thing to do is to write the number as a string, so I'm confused why he wants to avoid it, if that counts as "BigInt". In other words, just keep the number as an array of digits and perform multiplication manually in O(digits).

    → Reply