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