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.

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.

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 Reply