Medium Bit Manipulation

Adobe

Amazon

Facebook

Google

2020-05-29

137. Single Number II

Similar Question: LeetCode Question 136, LeetCode Question 260

Question:

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:

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

Example 1:

Input: [2,2,3,2]
Output: 3

Example 2:

Input: [0,1,0,1,0,1,99]
Output: 99

Solution:

Using HashMap to calculate the frequency of each elements.

class Solution {
    public int singleNumber(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i : nums)
          map.put(i, map.getOrDefault(i, 0) + 1);

        for (int k : map.keySet())
          if (map.get(k) == 1) return k;
        
        return -1;
    }
}

Using Bit Operation, one is the sum for every number that appears once which are not intersect with two. Two is the sum for every number that appears twice which do not intersect with one.

class Solution {
    public int singleNumber(int[] nums) {
        int one = 0;
        int two = 0;
        for (int i : nums) {
            one = (one ^ i) & (~two);
            two = (two ^ i) & (~one);
        }
        return one;
    }
}