Not-Afraid's blog

Help in Self Powers(Project Euler Hackerrank problem 48)
By Not-Afraid, history, 7 years ago, In English

I am getting TLE on last test case of this problem Link to the problem, i used Big mod Link to Big mod implmentation for multiplication while calculating power as we need last ten digits so we have to modulo it by 1e10 which will overflow in C++.

Any type of help is appreciated. Thanks in advance.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
7 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Not-Afraid (previous revision, new revision, compare).

→ Reply
»
7 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

BigMod implementation adds another factor of

Unable to parse markup [type=CF_MATHJAX]

, making the time complexity

Unable to parse markup [type=CF_MATHJAX]

.To remove the

Unable to parse markup [type=CF_MATHJAX]

factor, You can compute the remainder modulo

Unable to parse markup [type=CF_MATHJAX]

and $$$5^{10}$$$, and then find the remainder modulo $$$10^{10}$$$ using chinese remainder theorem.
→ Reply