Given an array where every element occurs three times, except one element which occurs only once. Find the element that occurs once. Expected time complexity is O(n) and O(1) extra space.
Excellent explanation from http://stackoverflow.com/questions/7338070/finding-an-element-in-an-array-where-every-element-is-repeated-odd-number-of-tim
Supposing every bit of numbers (including the unique number) in the input array is added. If the sum of a bit is multiple of 3, the corresponding bit in the unique number is 0. Otherwise, it is 1.
So idea here is to take 2 variable, say var1 and var2
1. var1 will keep a note that variable appeared first time.
2. var2 will keep a note that same variable appeared second time.
3. Now, when the same variable appears third time, we have to discard the element as number
appears 3 times which is fine and it is not the variable we are looking for.
Also, if the number appears 3 times properly, then we have to initialize var1 and var2 to 0 to
start looking for new element.
So for all the numbers which appears thrice, var1 and var2 will become 0 but only for number
which appears only once, var1 will be set with that value.
Lets take a simple example and see, given array is {1, 1, 1, 2}
1. 1st iteration encounter 1
secondTimeOccurence = 0
firstTimeOccurence = 1
2. 2nd iteration encounter 1
secondTimeOccurence = 1
firstTimeOccurence = 0
3. 3rd iteration encounter 1
secondTimeOccurence = 0
firstTimeOccurence = 0
4. 4th iteration encounter 2
secondTimeOccurence = 0
firstTimeOccurence = 2
Number that appear only once is present in variable firstTimeOccurence that is 2 here.
Read full article from Find the element that appears once | GeeksforGeeks
Excellent explanation from http://stackoverflow.com/questions/7338070/finding-an-element-in-an-array-where-every-element-is-repeated-odd-number-of-tim
the algorithm above does the following:
onesis the XOR of all elements that have appeared exactly once so fartwosis the XOR of all elements that have appeared exactly twice so far
int ones = 0;
int twos = 0;
int not_threes, x;
for (int i=0; i<n; ++i) {
x = A[i];
twos |= ones & x;
ones ^= x;
not_threes = ~(ones & twos);
ones &= not_threes;
twos &= not_threes;
}
Each time we take
x to be the next element in the array, there are three cases:- if this is the first time
xhas appeared, it is XORed intoones - if this is the second time
xhas appeared, it is taken out ofones(by XORing it again) and XORed intotwos - if this is the third time
xhas appeared, it is taken out ofonesandtwos.
Therefore, in the end,
ones will be the XOR of just one element, the lonely element that is not repeated. There are 5 lines of code that we need to look at to see why this works: the five after x = A[i].
If this is the first time
x has appeared, then ones&x=ones so twos remains unchanged. The line ones ^= x; XORs x with ones as claimed. Therefore x is in exactly one of ones and twos, so nothing happens in the last three lines to either ones or twos.
If this is the second time
x has appeared, then ones already has x (by the explanation above), so now twos gets it with the line twos |= ones & x;. Also, since ones has x, the line ones ^= x; removes xfrom ones (because x^x=0). Once again, the last three lines do nothing since exactly one of ones and twos now has x.
If this is the third time
x has appeared, then ones does not have x but twos does. So the first line let's twos keep x and the second adds x to ones. Now, since both ones and twos have x, the last three lines remove x from both.int getSingle(int arr[], int n){ int ones = 0, twos = 0 ; int common_bit_mask; // Let us take the example of {3, 3, 2, 3} to understand this for( int i=0; i< n; i++ ) { /* The expression "one & arr[i]" gives the bits that are there in both 'ones' and new element from arr[]. We add these bits to 'twos' using bitwise OR Value of 'twos' will be set as 0, 3, 3 and 1 after 1st, 2nd, 3rd and 4th iterations respectively */ twos = twos | (ones & arr[i]); /* XOR the new bits with previous 'ones' to get all bits appearing odd number of times Value of 'ones' will be set as 3, 0, 2 and 3 after 1st, 2nd, 3rd and 4th iterations respectively */ ones = ones ^ arr[i]; /* The common bits are those bits which appear third time So these bits should not be there in both 'ones' and 'twos'. common_bit_mask contains all these bits as 0, so that the bits can be removed from 'ones' and 'twos' Value of 'common_bit_mask' will be set as 00, 00, 01 and 10 after 1st, 2nd, 3rd and 4th iterations respectively */ common_bit_mask = ~(ones & twos); /* Remove common bits (the bits that appear third time) from 'ones' Value of 'ones' will be set as 3, 0, 0 and 2 after 1st, 2nd, 3rd and 4th iterations respectively */ ones &= common_bit_mask; /* Remove common bits (the bits that appear third time) from 'twos' Value of 'twos' will be set as 0, 3, 1 and 0 after 1st, 2nd, 3rd and 4th itearations respectively */ twos &= common_bit_mask; // uncomment this code to see intermediate values //printf (" %d %d \n", ones, twos); } return ones;}
Count sum of every bit
We can sum the bits in same positions for all the numbers and take modulo with 3. The bits for which sum is not multiple of 3, are the bits of number with single occurrence.
break each number into bits and then count how many times each bit is turned on and take that modulo n. If the result is 1, then it should be turned on in the answer. If it is 0, then it should be turned off.
http://codercareer.blogspot.com/2013/12/no-50-numbers-appearing-once.htmlint getSingle(int arr[], int n){ // Initialize result int result = 0; int x, sum; // Iterate through every bit for (int i = 0; i < INT_SIZE; i++) { // Find sum of set bits at ith position in all // array elements sum = 0; x = (1 << i); for (int j=0; j< n; j++ ) { if (arr[j] & x) sum++; } // The bits with sum not multiple of 3, are the // bits of element with single occurrence. if (sum % 3) result |= x; } return result;}break each number into bits and then count how many times each bit is turned on and take that modulo n. If the result is 1, then it should be turned on in the answer. If it is 0, then it should be turned off.
Supposing every bit of numbers (including the unique number) in the input array is added. If the sum of a bit is multiple of 3, the corresponding bit in the unique number is 0. Otherwise, it is 1.
int findUnique(int A[], int size) {
// First we set up a bit vector and initialize it to 0.
int count[32];
for (int j=0;j<32;j++) {
count[j] = 0;
}
// Then we go through each number in the list.
for (int i=0;i<size;i++) {
int x = A[i];
// And for each number we go through its bits one by one.
for (int j=0;j<32;j++) {
// We add the bit to the total.
count[j] += x & 1;
// And then we take it modulo 3.
count[j] %= 3;
x >>= 1;
}
}
// Then we just have to reassemble the answer by putting together any
// bits which didn't appear a multiple of 3 times.
int answer = 0;
for (int j=31;j>=0;j--) {
answer <<= 1;
if (count[j] == 1) {
answer |= 1;
}
}
return answer;
}So idea here is to take 2 variable, say var1 and var2
1. var1 will keep a note that variable appeared first time.
2. var2 will keep a note that same variable appeared second time.
3. Now, when the same variable appears third time, we have to discard the element as number
appears 3 times which is fine and it is not the variable we are looking for.
Also, if the number appears 3 times properly, then we have to initialize var1 and var2 to 0 to
start looking for new element.
So for all the numbers which appears thrice, var1 and var2 will become 0 but only for number
which appears only once, var1 will be set with that value.
secondTimeOccurence = secondTimeOccurence | (firstTimeOccurence & arr[i]);firstTimeOccurence = firstTimeOccurence ^ arr[i]; int neutraliser = ~(firstTimeOccurence & secondTimeOccurence);firstTimeOccurence = firstTimeOccurence & neutraliser;secondTimeOccurence = secondTimeOccurence & neutraliser;1. 1st iteration encounter 1
secondTimeOccurence = 0
firstTimeOccurence = 1
2. 2nd iteration encounter 1
secondTimeOccurence = 1
firstTimeOccurence = 0
3. 3rd iteration encounter 1
secondTimeOccurence = 0
firstTimeOccurence = 0
4. 4th iteration encounter 2
secondTimeOccurence = 0
firstTimeOccurence = 2
Number that appear only once is present in variable firstTimeOccurence that is 2 here.
private static int findElementThatAppearOnce(int arr[]){ int firstTimeOccurence = 0; int secondTimeOccurence = 0; for (int i=0; i < arr.length; i++){ secondTimeOccurence = secondTimeOccurence | (firstTimeOccurence & arr[i]); firstTimeOccurence = firstTimeOccurence ^ arr[i]; int neutraliser = ~(firstTimeOccurence & secondTimeOccurence); firstTimeOccurence = firstTimeOccurence & neutraliser; secondTimeOccurence = secondTimeOccurence & neutraliser; } return firstTimeOccurence; }