Can't understand time complexity

Правка en4, от pranp_24, 2023-05-31 07:44:45

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)