I coded and solved the problem with the O(N^2) solution (the one where you try out all possible a0).

However, the official solution has a bonus which asks you to come up with an O(N) solution.

I think I got the answer to the case where there is an even number of sums.
If the sums are b1, b2, …, bn - 1, where n is odd, I subtract the sum of b2 + b4 + … + bn - 1 from the total (which is n * (n + 1)), which gives me a0. Then, I can calculate the rest of the permutation.

But I can’t think of the O(N) solution to the case with the odd number of sums. Can anyone help? Thanks in advance.

Interesting! Sorry to bother you again, but how did you get to this solution?
I don’t quite understand why it works yet (e.g. why are there at most two values?).
Thanks!

@Benq
I solved it in O(N) using your solution! Thanks so much!
However, I’m still confused about why there are at most two values of a1. Can you help?
Thanks!