 # Find the only element in array which appears only once

Objec­tive: Given an array of integers, all the elements are appear twice but one element which appears only once. Write an algorithm to find that element.

Example:

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

Approach:

Brute Force:

Use nested loops and compare each element in array with all other elements and track the element which is non-repeated.

Time Complexity: O(n^2)

Code:

Use Hashing:

·      Store the count of each element in a hash map.

·      Iterate through hash map and return the element which has count 1.

Time Complexity: O(n) , Space Complexity: O(n)

Code:

Use XOR

·      We know that A XOR A = 0.

·      If we XOR all the elements in array, all the elements which are repeated twice will become 0 and remaining will the element which is appearing only once.

Code:

Output:

`Element appear only once in array – 4`

### 5 thoughts on “Find the only element in array which appears only once”

1. int[] a = { 1, 5, 6, 2, 1, 6, 4, 3, 2, 5, 3, 1, 3, 5 };
if (a.length == 0)
return;
int xor = a;
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 algorithm does not work.
Element appear only once in array – 3.

• Your input is wrong, please read the objective, it say all the elements are appearing TWICE but one. In your input there are elements which appears thrice

• got it.

2. This is the correct version of it. Your program doesn’t work and complexity is n^2 !!
public class XOR {

public static 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");
}
}
}
}
}

• 