### Finding a Single Number amongst Repeated Numbers [Repeated Twice]

Ever came across a problem which asks you to find a single number (or a number that occurs once) amongst a set of repeated numbers (which are repeated twice each) ? Well, it is a pretty common problem and is asked a lot of times.

There are many ways to solve the problem. The most obvious but inefficient approach to solve the problem would be to use a brute force approach where you can loop through the list multiple times to find the repeated numbers or you can have a count of all the numbers occurring and just return the number that has a count of 1. But an efficient way to solve the problem would be to use the bitwise operators.

The basic idea behind the solution is that XOR of two same numbers is 0.

We will simply loop through all the elements in the array and XOR each of them and save them in a variable.

So we will have 1 XOR 2 XOR 3 XOR 2 XOR 3. 2 XOR 2 and 3 XOR 3 would fetch 0, leaving us with 0 XOR 1. And this would obviously return 1 which is the solution. Simple right ?

There are many ways to solve the problem. The most obvious but inefficient approach to solve the problem would be to use a brute force approach where you can loop through the list multiple times to find the repeated numbers or you can have a count of all the numbers occurring and just return the number that has a count of 1. But an efficient way to solve the problem would be to use the bitwise operators.

The basic idea behind the solution is that XOR of two same numbers is 0.

**Problem**

**Sample Input :**1 2 3 2 3**Sample Output :**1We will simply loop through all the elements in the array and XOR each of them and save them in a variable.

So we will have 1 XOR 2 XOR 3 XOR 2 XOR 3. 2 XOR 2 and 3 XOR 3 would fetch 0, leaving us with 0 XOR 1. And this would obviously return 1 which is the solution. Simple right ?

**Code**

- #include <iostream>
- using namespace std;
- int main(int argc, const char * argv[]) {
- int n;
- cin>>n;
- int a[n];
- int res = 0;
- for(int i = 0; i < n; i++){
- cin>>a[i];
- res = res ^ a[i];
- }
- cout<<"Single Number : "<<res<<"\n";
- return 0;
- }

**Output**
## Comments

## Post a Comment