Currently, I encountered a question in interview "find a number which occurred odd time in Array". Friends in fact the first you think answer by using Hashtable and iterating all the elements from list and counting the number of time the element occurs in list.
But if is you remenber the college days and XOR digital gate this is very simple question to answer.
if the 1 XOR 1 = 0 and 1 XOR 0 = 1 so if same number are bitwise XORed it will give 0 and if odd time EXORed gives the number it self.
for ie 1 XOR 1 = 0 but 1 XOR 1 XOR 1 = 1 so here is simple program to find single number which occurred odd time in array.
But if is you remenber the college days and XOR digital gate this is very simple question to answer.
if the 1 XOR 1 = 0 and 1 XOR 0 = 1 so if same number are bitwise XORed it will give 0 and if odd time EXORed gives the number it self.
for ie 1 XOR 1 = 0 but 1 XOR 1 XOR 1 = 1 so here is simple program to find single number which occurred odd time in array.
public class FindOddOccuranceInArray {
public static void main(String[] arg) {
int[] nums = new int[] { 1,2,2};
int val = findOddOccur(nums);
System.out.println("val :: " + val);
}
public static int findOddOccur(int[] nums) {
int val = 0;
// all even number will be XORed to 0 and even number will
// remain
for (int i = 0; i < nums.length; i++) {
val ^= nums[i]; /bitwise xor
}
return val;
}
}
