Single Number

NeetCode: Single Number · LeetCode: 136. Single Number · Difficulty: Easy

Every element of nums appears exactly twice, except one that appears once. Return that single element, in linear time and constant extra space.

Example

Text

Input:  nums = [2, 2, 1]          Output: 1
Input:  nums = [4, 1, 2, 1, 2]    Output: 4

Brute force: count occurrences

Count each value in a HashMap<Integer, Integer> with merge, then return the key whose count is 1. Only one key has that count, so the unspecified HashMap iteration order does not affect the result. e.getValue() == 1 compares an Integer with an int, which unboxes the value, so it is a value comparison. It is linear time but needs a map as large as the number of distinct values.

Java

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

public class Main {
    static class Solution {
        public int singleNumber(int[] nums) {
            Map<Integer, Integer> counts = new HashMap<>();
            for (int x : nums) {
                counts.merge(x, 1, Integer::sum);
            }
            for (Map.Entry<Integer, Integer> e : counts.entrySet()) {
                if (e.getValue() == 1) {
                    return e.getKey();
                }
            }
            return 0;
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.singleNumber(new int[]{2, 2, 1}));
        System.out.println(s.singleNumber(new int[]{4, 1, 2, 1, 2}));
        System.out.println(s.singleNumber(new int[]{-7}));
    }
}

Output

1
4
-7

Time: O(n). Space: O(n).

Optimal: XOR everything

XOR has three properties: a ^ a = 0, a ^ 0 = a, and it is commutative and associative. XOR all numbers together and the paired values cancel each other in whatever order they appear, leaving only the value that appears once.

Example 4 ^ 1 ^ 2 ^ 1 ^ 2: reorder to (1 ^ 1) ^ (2 ^ 2) ^ 4 = 0 ^ 0 ^ 4 = 4.

Java

public class Main {
    static class Solution {
        public int singleNumber(int[] nums) {
            int acc = 0;
            for (int x : nums) {
                acc ^= x;
            }
            return acc;
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.singleNumber(new int[]{2, 2, 1}));
        System.out.println(s.singleNumber(new int[]{4, 1, 2, 1, 2}));
        System.out.println(s.singleNumber(new int[]{-7}));
    }
}

Output

1
4
-7

Time: O(n). Space: O(1).