Another puzzle that can be solved with eXclusive OR operator is to find the number that occurs odd number of times. The basic principle that XOR with the number itself x^x=0 results zero will solve this algorithmic puzzle.
Simple Algorithm to solve the puzzle
Below are the algorithmic steps for “Finding the number that occurs odd number of times“
- Have your numbers in array.
- Initialize the invariant x to zero.
- Loop through array elements and XOR with number x which is initialized to zero.
- All even set of numbers will be cleared out by XOR operation, the one repeating odd number of times will come out.
Implementation in Java
package com.jminded.algorithmicpuzzles;
public class FindNumberOccuringOddNoOfTimes {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
/**
* Finding element that occurs odd no.of times, the remaining elements are repeating even no.of times.
* x^x=0
*/
int[] arr={1,2,3,2,3,1,3};
int x=0;
for(int i=0;i<arr.length;i++){
x=x^arr[i];
System.out.println(x);
}
System.out.println("Result"+x);
}
}
Output:
3