Solving Single Number

To see the question, click here.

Naive Approach

To find the single element, we can first sort the array and then check for the single element. This approach works because each element appears twice except for one, and when the array is sorted, these elements appear adjacent. It becomes easy to identify the single element by checking these adjacent positions.

// TC: O(nlogn)
// SC: O(1)

import java.util.Arrays;

public class SingleNumber {
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i += 2) {
            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }
        return nums[nums.length - 1];
    }

    public static void main(String[] args) {
        SingleNumber sn = new SingleNumber();
        int[] nums = { 4, 1, 2, 1, 2 };
        System.out.println(sn.singleNumber(nums));
    }
}

Performance

The time complexity of the singleNumber method is O(nlogn) because of the sorting operation performed on the input array. The space complexity is O(1) because the algorithm uses constant extra space regardless of the input size.

Refined Approach

The idea is to use a HashSet to remember the element that has appeared only once. So, start iterating the array from the first position. If the element is not present in the HashSet then add that element. If the element is present in the HashSet , we have found a duplicate element, so remove that element from the HashSet. At last return the single element present in the HashSet .

// TC: O(n)
// SC: O(n)

import java.util.HashSet;

public class SingleNumber {
    public int singleNumber(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                set.remove(nums[i]);
            } else {
                set.add(nums[i]);
            }
        }

        for (int i : set) {
            ans = i;
        }
        return ans;
    }

    public static void main(String[] args) {
        SingleNumber sn = new SingleNumber();
        int[] nums = { 4, 1, 2, 1, 2 };
        System.out.println(sn.singleNumber(nums));
    }
}

Performance

The time complexity of the singleNumber method is O(n) because we iterate through the entire input array. The space complexity is also O(n) because we use a HashSet to store unique elements from the input array, potentially storing all n elements in the worst-case scenario.

Efficient Approach

X^X = 0

X^0 = X

Since we are dealing with repeated elements, let us try to solve using Bitwise XOR. When we XOR all the elements of the array, the elements that are repeated twice will get cancelled, and we finally get the element that is only present once.

// TC: O(n)
// SC: O(1)

public class SingleNumber {
    public int singleNumber(int[] nums) {
        int ans = nums[0];
        for (int i = 1; i < nums.length; i++) {
            ans ^= nums[i];
        }
        return ans;
    }

    public static void main(String[] args) {
        SingleNumber sn = new SingleNumber();
        int[] nums = { 4, 1, 2, 1, 2 };
        System.out.println(sn.singleNumber(nums));
    }
}

Performance

The time complexity of the singleNumber method is O(n) because it iterates through the entire array. The space complexity is O(1) because it uses constant extra space regardless of the input size.

Thank you for reading!

Check out other DSA patterns here.

You can support me by buying me a book.