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.

Problem

Sample Input : 1 2 3 2 3

Sample Output : 1

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 ?

Code 


  1. #include <iostream>  
  2.   
  3. using namespace std;  
  4.   
  5.   
  6. int main(int argc, const char * argv[]) {  
  7.       
  8.     int n;  
  9.     cin>>n;  
  10.     int a[n];  
  11.     int res = 0;  
  12.     for(int i = 0; i < n; i++){  
  13.         cin>>a[i];  
  14.         res = res ^ a[i];  
  15.     }  
  16.     cout<<"Single Number : "<<res<<"\n";  
  17.     return 0;  
  18. }  

Output


Comments

Popular posts from this blog

Finding the Longest Palindrome in a String

Finding the Longest Path From One Point To Another - Dynamic Programming