Find the element
that appears once
Given
an array where every element occurs two times, except one element which occurs
only once. Find
the element that occurs once?
Approach#1
By using
Brute Force technique, search for element which appeared once using two loops.
Complexity:
O (n^2).
Approach#2
1.
Sort the number.
2. Search
for the element appeared once.
Complexity:
O (nLogn).
Approach#3
Make
a hashmap which will maintain the count of each digit.
Complexity: Worst case time of
hashing may be more than O (n) and hashing requires extra space.
Approach#4
XOR
all the elements of the array and the result will be the element which appeared
once.
Complexity: O (n).
public class IdentifyNumber {
public static void main(String[] args) {
int[] array =
{11,3,4,5,4,3,6,7,6,7,5};
int num = indentifyNum(array);
System.out.println(num);
}
private static int indentifyNum(int[] array) {
int num = 0;
for (int
element : array) {
num = num ^ element;
}
return num;
}
}
Output: 11
No comments:
Post a Comment