Unique Element In Sorted Array

Nobita wants to impress Shizuka by correctly guessing her lucky number. Shizuka provides a sorted list where every number appears twice, except for her lucky number, which appears only once. Your task is to find this unique lucky number for Nobita.

Example:

Input:

T = 2
N = 7
list = [1, 1, 2, 2, 3, 4, 4]
N = 5
list = [5, 5, 7, 8, 8]

Output:

3
7

Explanation:

For the first test case, the number 3 appears only once in the list, whereas others appear twice. Similarly, for the second test case, the number 7 is the lucky number.

Constraints:

1

Question

Unique Element In Sorted Array

Nobita wants to impress Shizuka by correctly guessing her lucky number. Shizuka provides a sorted list where every number appears twice, except for her lucky number, which appears only once. Your task is to find this unique lucky number for Nobita.

Example:

Input:

T = 2
N = 7
list = [1, 1, 2, 2, 3, 4, 4]
N = 5
list = [5, 5, 7, 8, 8]

Output:

3
7

Explanation:

For the first test case, the number 3 appears only once in the list, whereas others appear twice. Similarly, for the second test case, the number 7 is the lucky number.

Constraints:

1 <= T <= 5
1 <= N <= 10⁵
0 <= data <= 10⁹ where ‘data’ is the value of elements in Shizuka’s list.
Time Limit: 1 sec

Note:

You do not need to print anything; the output should be returned by implementing the function provided.

Accepted Answer

Find the unique element in a sorted array where all other elements appear twice.

Use XOR operation to find the unique element in the sorted array.
Iterate through the array and XOR all elements, the result will be the unique element.
Time complexity of O(n) can be achieved by iterating through the array once.