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