Find the Unique Number in Java

In this problem, we are given an array of integers. In the given array, each element occurs two times except one element, which occurs only once. We have to find the number that appears only once. In this article, we are going to learn how we can find the number that appears once, and all other numbers appear twice in Java.

Scenario 1

All other numbers except 4 occur twice, so 4 is the only number that appears only once.

Input: [ 1, 2, 3, 3, 2, 4, 1, 5, 5]
Output: 4

Scenario 2

All other numbers except 10 appear two times, so 10 is the only number that appears only once.

Input: [ 7, 8, 9, 7, 10, 9, 11 ]
Output: 10

Below are different approaches for finding the number that appears twice, except one which occurs once in Java:

Brute Force Approach

In this approach, we use a nested loop to check each element in the array and count the number of times each element appears. We return the element that appears only once in the array.

Example

import java.util.*;
public class FindUniqueNumber {
    public static int findUnique(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (arr[i] == arr[j]) {
                    count++;
                }
            }
            if (count == 1) {
                return arr[i];
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] arr = {4, 3, 4, 5, 3};
        System.out.println("The number that appears once is: " + findUnique(arr));
    }
}

The output of the above program is as follows -

The number that appears once is: 5

Time Complexity: O(n2).

Efficient Approach Using XOR

The XOR operator has the following properties:

• a ^ a = 0, when any number is XORed with itself, then it will cancel out and result in zero.
• a ^ 0 = a, when any number is XORed with zero, then it will result in the same number.

XOR follows commutative and associative properties, which means that the order in which we apply XOR does not matter. The XOR approach is a more efficient approach. In this approach, we XOR all the elements of the array. All numbers occurring twice will cancel out with each other, and numbers that appear only once will be left out.

Example

import java.util.*;
public class FindUniqueNumber {
    public static int findUnique(int[] arr) {
        int answer = 0;
        for (int num : arr) {
            answer = answer ^ num;
        }
        return answer;
    }
    public static void main(String[] args) {
        int[] arr1 = {1, 2, 3, 3, 2, 4, 1, 5, 5};
        System.out.println("The number that appears once is: " + findUnique(arr1));
    }
}

The output of the above program is as follows -

The number that appears once is: 4

Time Complexity: O(n) .