TapeEquilibrium
test description:
well, for this question, the thinking process to optimize for time complexity took almost 20 mins (the whole test took me 30 mins to complete). Because the worst-case time complexity speculated was O(N), I could not do nested loops, which would make it super easy. So what I did is this ( to make the time complexity O(N) ):
It turns out I got 100% on the performance test (efficiency) but not on the correctness test:
so what the heck did I miss? yeap. turns out I have not followed the problem description where it says:
Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].
yes. 0 < P < N. I forgot this. I set it as 0 < P <= N as you can see from my code:
for ( int i = 0; i < A.length; i++) //this will cover ALL elements.
So, if you do:
int[] A = new int[2]; A[0] = 0; A[1] = 2000;
The current code will include 2000 in the variable leftPart for the last loop, which will cause the variable minDiff to be 0, not 2000. So just change that:
and now, there you go. Perfect score.