# Find the only element in array which appears only once

Objec­tive: Given an array of inte­gers, all the ele­ments are appear twice but one ele­ment which appears only once. Write an algo­rithm to find that element.

Exam­ple:

```int [] a = { 1,5,6,2,1,6,4,3,2,5,3};
output: 4
```

Approach:

Brute Force:

Use nested loops and com­pare each ele­ment in array with all other ele­ments and track the ele­ment which is non-repeated.

Time Com­plex­ity: O(n^2)

Code:

Use Hash­ing:

·      Store the count of each ele­ment in a hash map.

·      Iter­ate through hash map and return the ele­ment which has count 1.

Time Com­plex­ity: O(n) , Space Com­plex­ity: O(n)

Code:

Use XOR

·      We know that A XOR A = 0.

·      If we XOR all the ele­ments in array, all the ele­ments which are repeated twice will become 0 and remain­ing will the ele­ment which is appear­ing only once.

Code:

Out­put:

`Element appear only once in array – 4`

#### You may also like...

• Shams Mali

int[] a = { 1, 5, 6, 2, 1, 6, 4, 3, 2, 5, 3, 1, 3, 5 };
if (a.length == 0)
return;
int xor = a[0];
for (int i = 1; i < a.length; i++) {
xor ^= a[i];
}
System.out.println(“Element appear only once in array — ” + xor);

Fails for above input and I think this algo­rithm does not work.
Ele­ment appear only once in array — 3.

• tuto­ri­al­hori­zon

Your input is wrong, please read the objec­tive, it say all the ele­ments are appear­ing TWICE but one. In your input there are ele­ments which appears thrice

• Shams Mali

got it.

• Shams Mali

This is the cor­rect ver­sion of it. Your pro­gram doesn’t work and com­plex­ity is n^2 !!
pub­lic class XOR {

pub­lic sta­tic void main(String[] args) {
int[] a = { 1, 5, 6, 2, 1, 6, 4, 3, 2, 5, 3, 1, 3, 5 };
if (a.length == 0)
return;
for (int i = 0; i < a.length; i++) {
for (int y = 1; y < a.length; y++) {
if ((a[i] ^ a[y]) == 0) {
System.out.println(a[i] + ” repeated”);
}
}
}
}
}

• tuto­ri­al­hori­zon

The XOR solu­tion pro­vided has com­plex­ity O(n) (only one iter­a­tion) and the input pro­vided is wrong as per the objec­tive of the question