Блог пользователя Shinzy

Why is this giving TLE?
Автор Shinzy, история, 8 месяцев назад, По-английски

Here's The Problem Link:

Problem Link

I analyzed the Time Complexity of my code as O(T*N) and Space Complexity as O(1)

Which should technically satisfy the constrains given, But to my surprise it gives TLE on Test 3:

Here's My Java Submission:

Java Submission

Here's My Python Submission:

Python Submission

Please Help Me Out Guys!, Thanks For Your Valuable Time :)

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

»
8 месяцев назад, # |
← Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

The solution is doing a million string addition operations in the worst case, which is very expensive and take linear time.

Doing += to a string creates a new string every time. Maybe a string builder will help, but i don't know about python that much

→ Ответить
  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks For The Help, I really appreciate it!

    → Ответить
  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Because of the string operations he's not right about the time complexity. The string prepends take linear time, so the solution is actually $$$O(T*N^2)$$$

    → Ответить