Find the element that appears once

Find the element that appears once

Given an array where every element occurs two times, except one element which occurs only once. Find the element that occurs once?

Approach#1

By using Brute Force technique, search for element which appeared once using two loops.

Complexity: O (n^2).

Approach#2

1. Sort the number.

2. Search for the element appeared once.

Complexity: O (nLogn).

Approach#3

Make a hashmap which will maintain the count of each digit.

Complexity: Worst case time of hashing may be more than O (n) and hashing requires extra space.

Approach#4

XOR all the elements of the array and the result will be the element which appeared once.

Complexity: O (n).

public class IdentifyNumber {

     public static void main(String[] args) {

           int[] array = {11,3,4,5,4,3,6,7,6,7,5};

           int num = indentifyNum(array);

           System.out.println(num);

     }

     private static int indentifyNum(int[] array) {

           int num = 0;

           for (intelement : array) {

                num = num ^ element;

           }

           return num;

     }

}

Output: 11