Elements repeated thrice except one

[whiteflags]

Also, I cannot apply sorting as O(nlogn) would be necessary.

So what? It's only necessary as a prerequisite for a simple linear algorithm. Or, thinking about thinking, would you say binary search doesn't work in O(logn) time because it requires the array to be sorted, too? See, I think you're making this harder than it needs to be.