Find the only element in array which appears only once

Objective: 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);
	}
	}

view raw

EveryElementsRepeatedButOne.java

hosted with ❤ by GitHub

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

view raw

EveryElementsRepeatedButOne.java

hosted with ❤ by GitHub

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

view raw

EveryElementsRepeatedButOne.java

hosted with ❤ by GitHub

Output:

Element appear only once in array – 4

Related Posts: