dorasainath955's blog

Why does using logarithmic approach give me TLE?
By dorasainath955, history, 2 months ago, In English

Submission Problem

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

»
2 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Cause when k == 1 it will run n time which is of order 1e9.... But log approach still gives WA on larger tescase as it might have precision errors..

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

    could you give me an example for precision error, i mean int x = ln(n)/ln(k)

    we dont have to precisely find out the value of exponent, we can just find the one that's closest, could you give me an example where this approach will fail.

    i also did this approach, when n<k then there will be n operations, this also gave TLE

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

    Can you check this out:

    Comment-1203949

    I tried the log approach, one with multiples of k^x and one with just k^x. (Where k^x will be the largest power of k <= n)

    → Reply