137. Single Number II

Description

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?

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: [2, 2, 3, 2]

Output: 3

Example 2

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

Output: 99

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public int singleNumber(int[] nums) {
        if(nums.length == 0) return 0;
        
        int n = nums.length;
        if(n < 2) return nums[0];
        
        Arrays.sort(nums);
        
        // check if the first number is single
        if(nums[0] != nums[1]) return nums[0];
        
        // check if the last number is single
        if(nums[n-2] != nums[n-1]) return nums[n-1];
        
        for(int i = 1; i < n; i += 3) {
            if(nums[i-1] != nums[i]) return nums[i-1];
        }
        
        return 0;
    }
}

Solution 2

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> values = new HashMap();
        for(int n: nums) {
            values.put(n, values.getOrDefault(n, 0)+1);
        }
        for(int n: nums) {
            if(values.get(n) == 1) return n;
        }
        return 0;
    }
}

Solution 3

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public int singleNumber(int[] nums) {
        int seenOnce = 0, seenTwice = 0;

        for (int num : nums) {
            seenOnce = ~seenTwice & (seenOnce ^ num);
            seenTwice = ~seenOnce & (seenTwice ^ num);
        }

        return seenOnce;
    }
}

Follow up