Single Number II — LeetCode Interview Preparation Medium

Single Number II - LeetCode

The problem Single Number II requires us to find the one number whose frequency is one in the given list. Note that all the other numbers have exact frequency of three.

The most basic answer to this question, which is accepted in LeetCode would be to use a HashMap, and count each elements frequency as we move up the list. To save us time of sorting out the values later on, we simply remove each element that reaches a frequency of 3. This way the only remaining element in our HashMap would be the answer. The code would look like

class Solution {
    public int singleNumber(int[] nums) {
        HashMap<Integer,Integer> hmap = new HashMap<>();
        int res = 0;
        for(int i : nums){
            hmap.put(i, hmap.getOrDefault(i,0) + 1);
            if(hmap.get(i) == 3){
                hmap.remove(i);
            }
   
        }
        for(int i: hmap.keySet()) res = i;
        return res;
    }
}

Another, a more faster approach to this problem would be to simply sort the array and traverse the array finding the odd pair. This approach is relatively simpler. Once we have the sorted array, we can compare in pairs of 3, and if there is a mismatch, the first value of the mismatch would be the answer.

The only edge case here would be the last element of the array, which we simply return at the end. The could would look like

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

Now, the fastest one here would be using a bitwise operations which would look like

class Solution {
    public int singleNumber(int[] nums) {
       int ones=0,twos=0,three=0;
        for(int i=0;i<nums.length;i++){
            twos=twos | (nums[i] & ones);    
            ones=ones^nums[i];
            three=ones&twos;
            ones=ones& (~three);
            twos=twos&(~three);
        }
        return ones;
    }
}

Please like if this helped you. Thank you for reading.