Hi everyone,
I recently gone through Amazon interview process and was asked a question. I was not able to come with optimal approach during the interview and also didn't find any such question on internet.

Question:
Find the only non-repeating element where every other element repeat twice and duplicates are always together.
[5,5,3,3,1,2,2]

My Approach
I told O(n) approach by storing count in map. I also tried telling bit manipulation approach but he was not keen to listen other O(n) approach.

He insisted to tell a better approach. Obviously I was thinking of O(logn) approach. I tried thinking of binary search and divide and conquer but in the end complexity was coming same only.

Unfortunately during the interview I wasn't able to come up with any such approach.

Please tell in comments if anyone knows how to solve this problem optimally.

Thanks