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