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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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
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.
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.
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");
}
}
}
}
}
The XOR solution provided has complexity O(n) (only one iteration) and the input provided is wrong as per the objective of the question