Find a number occurring odd number of times in integer array using java

• Given an array of integer containing positive numbers.
• All number in an array is occurring even number of times except one number.
• We would like to find the number which occurs odd number of times.
• Let us understand the problem statement with examples.
  • int example1[] = { 1, 1, 2, 2, 3, 4, 4 };
  • int example2[] = { 10, 10, 10, 11, 11, 11, 11};
  • int example3[] = { 2, 2, 4, 4, 5 };
• In example1, numbers 1,2,4 occurs even number of times and 3 occurs odd times
• In example2, numbers 10 occurs odd number of times and 11 occurs even number of times.

Algorithm: find number occurring odd number of times in an array (java)

• We will use the properties of XOR gate.
• Truth table of “Exclusive-OR” or XOR gate is :

• Let us apply XOR gate on example1 = { 1, 1, 2, 2, 3, 4, 4 }
• OddNumber = 1 ^ 1 ^ 2 ^ 2 ^  3 ^ 4 ^ 4
• OddNumber = (1 ^ 1) ^ (2 ^ 2) ^  3 ^ (4 ^ 4)
• OddNumber = 0 ^ 0 ^  3 ^ 0
• OddNumber = 3.

Program: find the number occurring odd number of times in an array

package org.learn.arrays;

import java.util.Arrays;

public class NumberOddTimes {
	public static void main(String[] args) {

		int example1[] = { 1, 1, 2, 2, 3, 4, 4 };
		String array = Arrays.toString(example1);
		int oddNumber = getOddNumber(example1);
		System.out.printf("1. Number occur odd times in %s is: %d", array, oddNumber);

		int example2[] = { 10, 10, 10, 11, 11, 11, 11};
		array = Arrays.toString(example2);
		oddNumber = getOddNumber(example2);
		System.out.printf("\n2. Number occur odd times in %s is: %d", array, oddNumber);

		int example3[] = { 2, 2, 4, 4, 5 };
		array = Arrays.toString(example3);
		oddNumber = getOddNumber(example3);
		System.out.printf("\n3. Number occur odd times in %s is: %d", array, oddNumber);
	}

	private static int getOddNumber(int[] elements) {
		int oddNumber = elements[0];
		int length = elements.length;
		for (int index = 1; index < length; index++) {
			oddNumber ^= elements[index];
		}
		return oddNumber;
	}
}

Output: number occurring odd number of times in integer array (java)

1. Number occur odd times in [1, 1, 2, 2, 3, 4, 4] is: 3
2. Number occur odd times in [10, 10, 10, 11, 11, 11, 11] is: 10
3. Number occur odd times in [2, 2, 4, 4, 5] is: 5