ALT__'s blog

[Help] What's the time complexity of dividing (or % mod of) two big numbers?
By ALT__, history, 4 years ago, In English

So I was trying to solve this problem: Link

I got a TLE, my submission

I'm not sure if the solution is correct but I want to know why am I getting TLE, I think my solution is O(n), buy maybe because the numbers are too big I'm miscalculating something. I've added comments to my code too please let me know why is getting TLE. Thanks!

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

Comments Comments (2)
| Write comment?
»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

You have overflow here: i * i <= minn

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Note that you are dividing/modding by 64-bit numbers. Since the size is fixed, the operation takes O(1). Generally I think 64-bit is about twice as slow as 32-bit, but it is quite fast in any case. If you were dividing by arbitrarily large numbers, then it's implementation dependent but apparently it can be as fast as O(nlog n), where n is the number of bits in the number. I think the nlog n algorithm has a terrible constant though :P (https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Arithmetic_functions)

→ Reply