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:


public class EveryElementsRepeatedButOne {
public static void findBruteForce(int [] a){
boolean [] visited = new boolean[a.length];
for (int i = 0; i <a.length ; i++) {
int x = a[i];
if(visited[i]==false) {
boolean isDuplicate = false;
for (int j = i + 1; j < a.length; j++) {
if (x == a[j]) {
isDuplicate = true;
visited[j] = true;
}
}
if (!isDuplicate)
System.out.println("Element appear only once in array – " + x);
}
}
}
public static void main(String[] args) {
int [] a = { 1,5,6,2,1,6,4,3,2,5,3};
findBruteForce(a);
}
}


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:


import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;
public class EveryElementsRepeatedButOne {
public static void findByHashing(int [] a){
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i <a.length ; i++) {
if(map.containsKey(a[i])) {
int count = map.get(a[i]);
map.put(a[i],++count);
}else
map.put(a[i],1);
}
Set<Integer> set = map.keySet();
Iterator<Integer> iterator = set.iterator();
while (iterator.hasNext()){
int key = iterator.next();
if(map.get(key)==1){
System.out.println("Element appear only once in array – " + key);
}
}
}
public static void main(String[] args) {
int [] a = { 1,5,6,2,1,6,4,3,2,5,3};
findByHashing(a);
}
}


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:


public class EveryElementsRepeatedButOne {
public static void findUsingXOR(int [] a){
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);
}
public static void main(String[] args) {
int [] a = { 1,5,6,2,1,6,4,3,2,5,3};
findUsingXOR(a);
}
}

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[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 algorithm does not work.
    Element appear only once in array – 3.

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

    Reply
    • The XOR solution provided has complexity O(n) (only one iteration) and the input provided is wrong as per the objective of the question

      Reply

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.