Single Element :
Difficulty Level : Medium
Submissions : 1018
Asked In :
Marks :15
: 5 | : 1
You are given an array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. It is also guaranteed that the duplicate occurrences occur consecutively.
Return the single element that appears only once.
Your solution must run in O(log n) time and O(1) space.
The first line of input contains an integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of testcases. The description of $$$t$$$ testcases follows.
The first line of each testcase contains an integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^{5})$$$ — the size of array $$$A$$$.
The second line of each testcase contains $$$n$$$ space separated integers $$$a_1, a_2,... a_n$$$ $$$(-10^9 \le a_i \le 10^9)$$$ — the elements of array $$$A$$$.
It is guaranteed that sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$ and every element appears exactly twice consecutively, except for one element which appears exactly once.
For each test case, print the element that appears exactly once in a single line.
291 1 2 3 3 4 4 8 873 3 7 7 10 11 11
2 10
