Problem: 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.
Examples:
Input: arr[] = {10, 1, 10, 3, 10, 1, 1, 2, 3, 3}
Output: 2
Solution:
If O(1) space constraint was not there, we could’ve gone for a hashmap with values being the count of occurrences. But since there is space constraint we can go for bitwise operations.
Basically, it makes use of the fact that x^x = 0 and 0^x=x. So all paired elements get XOR’d and vanish leaving the lonely element.
If a bit is already in ones, add it to twos.
XOR will add this bit to ones if it’s not there or remove this bit from ones if it’s already there.
If a bit is in both ones and twos, remove it from ones and twos.
When finished, ones contains the bits that only appeared 3*n+1 times, which are the bits for the element that only appeared once.
int getUniqueElement(int[] arr)
{
//this variable holds XOR of all the elements which have appeared "only" once.
int ones = 0 ;
//this variable holds XOR of all the elements which have appeared "only" twice.
int twos = 0 ;
int not_threes ;
for( int x : arr )
{
twos |= ones & x ; //add it to twos if it exists in ones
ones ^= x ; //if it exists in ones, remove, otherwise, add it
// Next 3 lines of code just converts the common 1's between "ones" and "twos" to zero.
//if x is in ones and twos, dont add it to Threes.
not_threes = ~(ones & twos) ;
ones &= not_threes ;//remove x from ones
twos &= not_threes ;//remove x from twos
}
return ones;
}
I don’t understand the logic. will anyone explain what is the logic behind this question
Logic: An element when XORed with itself returns 0 and an element when XORed with 0 returns itself. So, on traversing the complete array once and XORing all elements the elements that are repeating are removed and we get the element that is present odd number of times.
Thank You!
HAPPY CODING.
my solution:
int getuniqueElement(int arr[], int n)
{
int res = arr[0];
for(int i =1; i<n; i++)
{
res = res^ a[i];
}
printf("the elements without repitition is %d\n", res);
}
int main()
{
int a[10] = {10, 1, 10, 3, 10, 1, 1, 2, 3, 3};
int n;
n = sizeof(a) / sizeof(a[0]);
getUniqueElement(a,n);
}