Find Single Number from array

Write a program to Find a Single Number from an array.

 Example 1:

Input: nums = { 2, 2, 1, 3, 1 }
Output: 3

Approach 1: Using Hashmap (Java), map (C++) 

Java

import java.util.HashMap;

public class FindSingleNumber {
    public static void main(String[] args) {
        int[] nums = { 2, 2, 1, 3, 1 };
        int single = singleNumber(nums);
        System.out.println("Single number is " + single);
    }

    // method for find single number
    public static int singleNumber(int[] nums) {
        // create map for hold frequency of number
        HashMap<Integer, Integer> map = new HashMap<>();
        // Iterate till end of array
        for (int i = 0; i < nums.length; i++) {
            // add in map based on condition
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        // find single number from map
        for (int key : map.keySet()) {
            // if single number the return
            if (map.get(key) == 1) {
                return key;
            }
        }
        return 0;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
//function to find the single element
//in the array ,array contains all element twice
//except the one element
int singleElement(int arr[],int n)
{
    //map to hold the count of 
    //all the number
    map<int,int> mp;
    for(int i=0;i<n;i++)
      {
        //increment the count of
        //current element
          mp[arr[i]]++;
      }
    
    //initialize the single element as arr[0]
    int single=arr[0];
   
   //iterate the map
    for(auto it=mp.begin();it!=mp.end();it++)
       {
           //if frequency is 1
           if(it->second==1)
             {
                 //store the single as the current 
                 //element
                 single=it->first;
                 break;
             }
       }
    //return the single element
    return single;
}
int main()
{
    int arr[]={2,2,1,3,1};

    //find the length of array
    int n=sizeof(arr)/sizeof(arr[0]);
    int single=singleElement(arr,n);
    cout<<"Single element is ";
    cout<<single<<"\n";
    return 0;
}

Approach 2: Using XOR (because xor of two same number becomes 0)

Java

public class FindSingleNumber {
    public static void main(String[] args) {
        int[] nums = { 2, 2, 1, 3, 1 };
        int single = singleNumber(nums);
        System.out.println("Single number is " + single);
    }

    // method for find single number
    public static int singleNumber(int[] nums) {
        int singleElement = nums[0];
        // Iterate till end of array
        for (int i = 1; i < nums.length; i++) {
            // XOR manipulation
            singleElement = singleElement ^ nums[i];
        }

        return singleElement;
    }
}

C++

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

//function to find the single
//element of the array
//array contains all elements twice
//execpt the one element which occur 
//one time
int singleElement(int arr[],int n)
{
    int single=arr[0];

    //iterate for all the 
    //element of the array
    for(int i=1;i<n;i++)
      {
          //update single element as 
          //single =single^arr[i]
          //xor of 2 same number beomes 0
          single=single^arr[i];
      }

    //return the single element
    return single;
}
int main()
{
    int arr[]={2,2,1,3,1};

    //find the length of array
    int n=sizeof(arr)/sizeof(arr[0]);
    int single=singleElement(arr,n);
    cout<<"Single element is ";
    cout<<single<<"\n";
    return 0;
}