Find Odd Occurrence Number Array in Java

Find Odd Occurrence Number Array In Java | In this section, we will find the elements which have occurred an odd number of times in an array. Let us see some examples to have a better understanding of the problem:-

1) array = {1, 2, 3, 4, 5, 5, 5, 1, 2, 3, 4}
Odd occurrence number in array = 5

2) array = {10, 20, 10, 30, 10, 20, 40, 20, 20, 40}
Odd occurrence number in array = 10, 30

Program to Find Odd Occurrence Number Array in Java

In the given array if only one element occurs the odd number of times and all the other elements occur an even number of times, in that case, we can use the below program to find the odd occurrence number array in Java.

public class Main {
   public static int oddOccurrence(int array[]) {
      for (int i = 0; i < array.length; i++) {
         int count = 0;
         for (int j = 0; j < array.length; j++) {
            if (array[i] == array[j])
               count++;
         }
         if (count % 2 != 0)
            return array[i];
      }
      return -1;
   }

   public static void main(String[] args) {
      int array[] = new int[] { 10, 50, 60, 50, 41, 10, 60 };
      System.out.println(oddOccurrence(array));
   }
}

Output:-

41

But if the array contains multiple elements which occur the odd number of times then this program returns only the first element which occurs the odd number of times. To solve this problem we can take the help of the HashMap.

Program to Find Odd Occurrence Number Array in Java using HashMap

In HashMap we will store the element as key and its occurrence as value. Later we will iterate the HashMap to check for the number which occurs an odd number of times and return them to the caller method.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;

public class Main {

   public static Integer[] oddOccurrence(int array[]) {
      HashMap<Integer, Integer> hashmap = new HashMap<>();
      for (int i = 0; i < array.length; i++) {
         if (hashmap.containsKey(array[i])) {
            int existingCount = hashmap.get(array[i]);
            hashmap.put(array[i], existingCount + 1);
         } else {
            hashmap.put(array[i], 1);
         }
      }

      List<Integer> list = new ArrayList<>();
      for (Integer a : hashmap.keySet()) {
         if (hashmap.get(a) % 2 != 0) {
            list.add(a);
         }
      }
      return list.toArray(new Integer[] {});
   }

   public static void main(String[] args) {
      Scanner scan = new Scanner(System.in);
      System.out.print("Enter number of array elements: ");
      int length = scan.nextInt();
      int[] array = new int[length];
      System.out.println("Enter array elements: ");
      for (int i = 0; i < length; i++) {
         array[i] = scan.nextInt();
      }
      System.out.println("Original array: " 
                        + Arrays.toString(array));

      Integer[] newArray = oddOccurrence(array);
      if (newArray.length > 0) {
         System.out.println("Elements which occur " 
            +"odd number of times: " 
            + Arrays.toString(newArray));
      } else {
         System.out.println("All element occur even number of times");
      }
      scan.close();
   }
}

Output:-

Enter number of array elements: 9
Enter array elements:
10 20 31 31 51 51 31 10 15
Original array: [10, 20, 31, 31, 51, 51, 31, 10, 15]
Elements which occur odd number of times: [20, 31, 15]

Enter number of array elements: 5
Enter array elements:
10 15 10 25 30
Original array: [10, 15, 10, 25, 30]
Elements which occur odd number of times: [25, 30, 15]

Enter number of array elements: 6
Enter array elements:
10 20 30 10 20 30
Original array: [10, 20, 30, 10, 20, 30]
All element occur even number of times

In the above program to find odd occurrence number array in Java using HashMap, we find the occurrence of each element and stored them in the hashmap. Later we created an ArrayList and iterated through the hashmap. If the element occurs the odd number of times then we store them in the arraylist. Finally we have converted the ArrayList to an array and returned them to the caller method.

In the above program to display the array, we have used the toString() method. The toString() method of the Java Array class is used to convert an array to a string.

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!