Java Interview Questions - Find the number occurring odd number of times in an array

• findOddOccuranceUsingForLoop -
  We can use two nested for loops to find the array element whose occurrence is odd number of times.
  
  During the first for loop the element is selected from the array and then during the second nested for loop we again iterate the array to find how many times it occurs in the array. So it's time complexity is O(N^2).
• findOddOccuranceUsingMap -
  We can use Hashmap to find the array element whose occurrence is odd number of times. During the first for loop the all elements are inserted in the map. The elements of the array are the keys and their occurrence count are the values in the map.
  
  Using the second for loop we again iterate the hashmap to find the element with value i.e the occurrence which is an odd value. We use 2 for loops. But the for loops are not nested but used sequentialy so it's time complexity is O(N+N) which is O(N).
• findOddOccuranceUsingXOR -
  We can use the XOR operation to find the array element whose occurrence is odd number of times.
  
  We initialize a variable result with value 0.
  
  Then during the for loop the result is XORed with all elements of the array. The time complexity is O(N).

package com.javastructures;

import java.util.HashMap;
import java.util.Map;

public class FindOddOccurancesInArray {

	public static void main(String args[]) {
		int arr[] = { 1, 1, 2, 2, 3, 3, 3 };
		findOddOccuranceUsingForLoop(arr);
		findOddOccuranceUsingMap(arr);
		findOddOccuranceUsingXOR(arr);
	}

	private static void findOddOccuranceUsingForLoop(int arr[]) {

		int countOccurance;
		// iterate over each occurance and
		// then find its count using 2 for loops
		for (int i = 0; i < arr.length; i++) {
			countOccurance = 0;
			for (int j = 0; j < arr.length; j++) {
				if (arr[i] == arr[j]) {
					countOccurance++;
				}
			}
			if (countOccurance % 2 == 1) {
				System.out.println("The odd occurance using for loop is " + arr[i]);
				break;
			}
		}

	}

	private static void findOddOccuranceUsingMap(int arr[]) {

		Map<Integer, Integer> map = new HashMap<>();
		// Iterate over the array and using map calculate the count
		for (int i = 0; i < arr.length; i++) {
			if (map.get(arr[i]) == null) {
				map.put(arr[i], 1);
			} else {
				int count = map.get(arr[i]);
				map.put(arr[i], ++count);
			}
		}
		for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
			if (entry.getValue() % 2 == 1) {
				System.out.print("The odd occurance using Map is " + entry.getKey());
				break;
			}
		}
	}

	private static void findOddOccuranceUsingXOR(int arr[]) {

		int result = 0;
		// Iterate over the array and using XOR calculate the element occuring
		// odd number of times
		for (int i = 0; i < arr.length; i++) {
			result = result ^ arr[i];
		}
		System.out.print("The odd occurance using XOR is " + result);
	}

}