code.blood's blog

By code.blood, history, 5 years ago, In English

I recently saw at one blog , A code is executed like that

N + N/2 + N/3 + N/4 + ....... + N/N

and author of this code saying

N + N/2 + N/3 + N/4 + ....... + N/N = O(N log(N) ) ? How ?

We know complexity of something is divided by 2 , become log2(N) . For example binary search's worst case complexity is O(log2(N) ) . But how the upper snippet

N + N/2 + N/3 + N/4 + ....... + N/N

equals to O(N log2(N) ) ? Can anyone explain it ?

Read more »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

By code.blood, 5 years ago, In English

Hello codeforces community , I am facing with that problem . For the input 12 how output is 5 ?

My solution is :

at time 0 we jump from 0 to 1 co-ordinate

at time 1 we jump from 1 to 3 co-ordinate

at time 2 we jump from 3 to 6 co-ordinate

at time 3 we dont jump because now jump length will be 4 , since we are on co-ordinate 6 so if we jump we will be on 6+4=10 co-ordinate ,

at time 4 we dont jump because now jump length will be 5 , since we are on co-ordinate 6 so if we jump we will be on 6+5=10 co-ordinate ,

at time 5 we will jump because now jump length will be 6 , since we are on co-ordinate 6 so if we jump we will be on 6+6=12 co-ordinate . We reached on co-ordinate 12 at time 6 . because one jump takes one second (5+1=6) .

So ans should be 6 . Why 5 ?

Read more »

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it