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
YouTube
Examples
Input: [2, 2, 3, 2]
Output: 3
Input: [0, 1, 0, 1, 0, 1, 99]
Output: 99
Solutions
/**
* 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;
}
}
/**
* 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;
}
}
/**
* 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;
}
}