Add the solution for another version :

Each element in array a[] is unique, allowed to use extra O(n) space.
But the time complexity must be O(n).