Finding the number that occurs odd number of times

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

  1. Have your numbers in array.
  2. Initialize the invariant x to zero.
  3. Loop through array elements and XOR with number x which is initialized to zero.
  4. 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

Leave a Comment