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

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

Solution 3

Follow up