Single Number

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.

Example

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

Output : 2

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

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.

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(n²) 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[ ].

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

References