Single Number  

Difficulty Level Easy
Frequently asked in Amazon
Array

Given an array a[ ] of size n. All the elements in the array are present twice except for 1. Find the element which appears only once or in other words we say that find the single number.

Single NumberPin

Example  

Input : a[ ] = {1, 3, 5, 5, 2, 1, 3}

Output : 2

Input : a[ ] = {1, 3, 5, 5, 1}

Please click Like if you loved this article?

Output : 3

Simple Method  

Check each element with every other element. Return the single element.

Algorithm

  1. Initialize an array a[] of size n.
  2. Create an integer variable to store the single element in the array and initialize a flag variable as 0.
  3. Traverse through the array and update the flag variable as 0 and the variable for the single element as the value stored at the current index in array a[ ].
  4. Create an inner loop from 0 to n-1 and check if the value stored at current index in array a[ ] is equal to the variable for the single element and the current index of the inner loop is not equal to the current index of the outer loop, update the flag variable as 1.
  5. If the flag variable is equal to 0, return the variable for the single element.
See also
Check if the given array can represent Level Order Traversal of Binary Search Tree

C++ Program to find a single number

#include <bits/stdc++.h>
using namespace std;

int singleElement(int a[], int n){
    int single,flag=0;
    for(int i=0; i<n; i++){
        flag = 0;
        single = a[i];
        for(int j=0; j<n; j++){
            if((a[j]==single)&&(j!=i)){
                flag=1;
            }    
        }
        if(flag==0)
            return single;
    }
}

int main() {
  int a[] = {1, 3, 5, 5, 2, 1, 3};
  int n = sizeof(a)/sizeof(a[0]);
  cout<<singleElement(a, n);
  return 0;
}
2

Java Program to find a single number

class unique{ 
    
    static int singleElement(int[] a, int n){
        int single=0,flag=0;
        for(int i=0; i<n; i++){
            flag = 0;
            single = a[i];
            for(int j=0; j<n; j++){
                if((a[j]==single)&&(j!=i)){
                    flag=1;
                }    
            }
            if(flag==0){
                return single;
            }    
        }
        return single;
    }

    public static void main (String[] args){ 
  
        int a[] = {1, 3, 5, 5, 2, 1, 3}; 
        int n = a.length; 
        System.out.println(singleElement(a, n)); 
        
    } 
} 
2

Complexity Analysis

Time Complexity: O(n2) where n is the number of elements in the given array a[ ].

Auxiliary Space: O(1) because we used constant extra space.

Using Xor  

Using properties of xor –

a xor a = 0

0 xor a = a

Algorithm

  1. Initialize an array a[] of size n.
  2. Create the function to find the single element in the given array a[ ] which accepts an integer array and the size of the integer array as it’s a parameter.
  3. Initialize a variable single and store the first element of the given array in it.
  4. Traverse through the array from 1 to n-1 and update the variable single as the xor of the variable single itself and the value at the current index in the given array.
  5. Return the variable single.

C++ Program to find a single number

#include <bits/stdc++.h>
using namespace std;

int singleElement(int a[], int n){
    int single = a[0]; 
    for(int i=1; i<n; i++) 
        single = single ^ a[i]; 
  
    return single;
}

int main() {
  int a[] = {1, 3, 5, 5, 2, 1, 3};
  int n = sizeof(a)/sizeof(a[0]);
  cout<<singleElement(a, n);
  return 0;
}
2

Java Program to find a single number

class unique{ 
    
    static int singleElement(int[] a, int n){
        int single = a[0]; 
        for(int i=1; i<n; i++) 
            single = single ^ a[i]; 
      
        return single;
    }

    public static void main (String[] args){ 
  
        int a[] = {1, 3, 5, 5, 2, 1, 3}; 
        int n = a.length; 
        System.out.println(singleElement(a, n)); 
        
    } 
} 
2

Complexity Analysis

Time Complexity: O(n) where n is the number of elements in the given array a[ ].

See also
Find k-th smallest element in BST (Order Statistics in BST)

Auxiliary Space: O(1) because we used constant extra space.

References

Please click Like if you loved this article?