Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

HashMap O(n) time O(n) space solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public int singleNumber(int[] nums) {
        if (nums == null || nums.length < 1){return -1;}
        HashMap<Integer,Integer> counts = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++){
            if (counts.containsKey(nums[i])){
                int count = counts.get(nums[i]);
                if (count == 2){
                    counts.remove(nums[i]);
                }else{
                    counts.put(nums[i], count + 1);
                }
            }else{
                counts.put(nums[i], 1);
            }
        }
        
        Set<Map.Entry<Integer, Integer>> num = counts.entrySet();
        Iterator<Map.Entry<Integer, Integer>> it = num.iterator();
        Map.Entry<Integer, Integer> entry = it.next();
        return entry.getKey();
    }
}

Bit solution

Explanation

1
2
3
4
5
6
7
8
9
10
public class Solution {
    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0;
        for (int i = 0; i < nums.length; i++){
            ones = (ones ^ nums[i]) & ~twos;
            twos = (twos ^ nums[i]) & ~ones;
        }
        return ones;
    }
}