Doubt in Stupid Machine

Link-CodeChef: Practical coding for everyone
how my solution doesn’t give TLE? even though my sol is n^2 and constraints are of O(n).
is there any efficient solution for O(n)?

Your code is amortised O(n\log{n}), because, the minimum can be anywhere, so on average it will be in the middle and your index will get halved every iteration. Your code will get it’s worst case O(n^2) in the test case

1
1000000
1000000 999999 999998 ....   1

The O(n) solution is to notice any box can only get the minimum of itself and all the boxes before it.
https://www.codechef.com/viewsolution/31864689

1 Like