Can't understand time complexity

Правка en1, от pranp_24, 2023-05-31 07:41:02

I was just working on a problem and I can't understand why one of my solutions passed and the other didn't.

I have two loops that are the same complexity. Since they are the same complexity, it should simplify to O(N)+O(N)=O(2N) which just becomes O(N). When I take out one of the loops, my solution passes, but when I keep them both in I get TLE. I don't understand this since they should simplify to the same complexity. Can someone please help?

Not accepted solution:

while(number>0){ if(number % 2==0){ stack.add(1); } else{ stack.add(2); } number/=2; }

int originalsize= stack.size(); for (int i = 0; i < originalsize; i++) { System.out.print(stack.pop()+ " "); }

Accepted solution:

String ans=""; while(number>0){ if(number % 2==0){ ans="1 "+ans; } else{ ans="2 "+ans; } number/=2; } System.out.println(ans);

Problem link: https://codeforces.net/contest/1810/problem/B Accepted Solution: https://codeforces.net/contest/1810/submission/207920289 Not accepted Solution: https://codeforces.net/contest/1810/submission/207919439

Теги time complexity

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский pranp_24 2023-05-31 07:44:45 6
en3 Английский pranp_24 2023-05-31 07:43:45 68
en2 Английский pranp_24 2023-05-31 07:41:53 40
en1 Английский pranp_24 2023-05-31 07:41:02 1173 Initial revision (published)