Single Element DSA Problem Solution

Single Element DSA Problem Solution

by

In this post, we are going to solve Single Element DSA Problem from Flipkart Online assessment. Let’s have a look at the problem statement first and then try to solve the problem.

Single Element DSA Problem Statement

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.

Input

The first line of input contains an integer

t

(1≤t≤104) — the number of testcases. The description of

t testcases follows.

The first line of each testcase contains an integer

n

(1≤n≤2⋅105) — the size of array

A.

The second line of each testcase contains

n space separated integers

a1,a2,...an

(−109≤ai≤109) — the elements of array

A.

It is guaranteed that sum of

n over all test cases does not exceed

2⋅105 and every element appears exactly twice consecutively, except for one element which appears exactly once.

Output

For each test case, print the element that appears exactly once in a single line.

Example
Input
2
9
1 1 2 3 3 4 4 8 8
7
3 3 7 7 10 11 11
Output
2
10

Problem Solution in C++
#include <bits/stdc++.h>
using namespace std;


void solve()
{

int n;
cin >> n;

vector<int> a(n);

for(auto &i : a)cin >> i;

int s = 0 , e = n-1;

while(s<e)
{
int mid = (s+e)/2;
if(mid%2==1)mid--;
if(a[mid] != a[mid+1])e = mid;
else s = mid+2;
}
cout << a[s] << endl;
}
int main()
{
int t;
cin >> t;
while(t--)
{
solve();
}

return 0;
}
Leave a Comment