Question
Formatted question description: https://leetcode.ca/all/137.html
137 Single Number II
Given an array of integers, every element appears three times except for one. Find that single one.
Example 1:
Input: [2,2,3,2]
Output: 3
Example 2:
Input: [0,1,0,1,0,1,99]
Output: 99
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
@tag-bit
Algorithm
A 32-bit number can be created to count the number of occurrences of 1 in each digit. If a certain digit is 1, then if the integer appears three times, the remainder of 3 is 0, so that the numbers of each digit position are added up then take the remainder of 3, and the final number remaining is a single number.
Code
Java
public class Single_Number_II {
public class Solution {
public int singleNumber(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
// first doubt, how long bits should I check.
// int is 32 bit, so bitmap length is 32
int single = 0;
for (int bitPos = 0; bitPos < 32; bitPos++) {
int sumAtThisPos = 0;
for (int j = 0; j < nums.length; j++) {
int digitInA = ((nums[j] >> bitPos) & 1);
sumAtThisPos += digitInA;
}
int afterMod = sumAtThisPos % 3;
single |= (afterMod << bitPos);
}
return single;
}
}
}