CareerCup

Found this solution
Question: You are given an array that contains integers. The integers content is such that every integer occurs 3 times in that array leaving one integer that appears only once.

Fastest way to find that single integer
eg:
Input: [2,1,4,5,1,4,2,2,4,1]
Answer: 5

Answer: I couldn't solve this question myself at first go in O(n) with O(1) space. Searched for it and found an excellent answer here. Sharing the answer and explanation for that:

int main()
{
int B[] = {1,1,1,3,3,3,20,4,4,4};
int ones = 0 ;
int twos = 0 ;
int not_threes, x ;

for( i=0; i< 10; i++ )
{
x = B[i];
twos |= ones & x ;
ones ^= x ;
not_threes = ~(ones & twos) ;
ones &= not_threes ;
twos &= not_threes ;
}

printf("\n unique element = %d \n", ones );
return 0;
}



Explanation:
The code works in similar line with the question of "finding the element which appears once in an array - containing other elements each appearing twice". Solution is to XOR all the elements and you get the answer.

Basically, it makes use of the fact that x^x = 0. So all paired elements get XOR'd and vanish leaving the lonely element.
Since XOR operation is associative, commutative.. it does not matter in what fashion elements appear in array, we still get the answer.

Now, in the current question - if we apply the above idea, it will not work because - we got to have every unique element appearing even number of times. So instead of getting the answer, we will end up getting XOR of all unique elements which is not what we want.

To rectify this mistake, the code makes use of 2 variables.
ones - At any point of time, this variable holds XOR of all the elements which have
appeared "only" once.
twos - At any point of time, this variable holds XOR of all the elements which have
appeared "only" twice.

So if at any point time,
1. A new number appears - It gets XOR'd to the variable "ones".
2. A number gets repeated(appears twice) - It is removed from "ones" and XOR'd to the
variable "twice".
3. A number appears for the third time - It gets removed from both "ones" and "twice".

The final answer we want is the value present in "ones" - coz, it holds the unique element.

So if we explain how steps 1 to 3 happens in the code, we are done.
Before explaining above 3 steps, lets look at last three lines of the code,

not_threes = ~(ones & twos)
ones & = not_threes
twos & = not_threes

All it does is, common 1's between "ones" and "twos" are converted to zero.

For simplicity, in all the below explanations - consider we have got only 4 elements in the array (one unique element and 3 repeated elements - in any order).

Explanation for step 1
------------------------
Lets say a new element(x) appears.
CURRENT SITUATION - Both variables - "ones" and "twos" has not recorded "x".

Observe the statement "twos| = ones & x".
Since bit representation of "x" is not present in "ones", AND condition yields nothing. So "twos" does not get bit representation of "x".
But, in next step "ones ^= x" - "ones" ends up adding bits of "x". Thus new element gets recorded in "ones" but not in "twos".

The last 3 lines of code as explained already, converts common 1's b/w "ones" and "twos" to zeros.
Since as of now, only "ones" has "x" and not "twos" - last 3 lines does nothing.

Explanation for step 2.
------------------------
Lets say an element(x) appears twice.
CURRENT SITUATION - "ones" has recorded "x" but not "twos".

Now due to the statement, "twos| = ones & x" - "twos" ends up getting bits of x.
But due to the statement, "ones ^ = x" - "ones" removes "x" from its binary representation.

Again, last 3 lines of code does nothing.
So ultimately, "twos" ends up getting bits of "x" and "ones" ends up losing bits of "x".

Explanation for step 3.
-------------------------
Lets say an element(x) appears for the third time.
CURRENT SITUATION - "ones" does not have bit representation of "x" but "twos" has.

Though "ones & x" does not yield nothing .. "twos" by itself has bit representation of "x". So after this statement, "two" has bit representation of "x".
Due to "ones^=x", after this step, "one" also ends up getting bit representation of "x".

Now last 3 lines of code removes common 1's of "ones" and "twos" - which is the bit representation of "x".
Thus both "ones" and "twos" ends up losing bit representation of "x".

1st example
------------
2, 2, 2, 4

After first iteration,
ones = 2, twos = 0
After second iteration,
ones = 0, twos = 2
After third iteration,
ones = 0, twos = 0
After fourth iteration,
ones = 4, twos = 0

2nd example
------------
4, 2, 2, 2

After first iteration,
ones = 4, twos = 0
After second iteration,
ones = 6, twos = 0
After third iteration,
ones = 4, twos = 2
After fourth iteration,
ones = 4, twos = 0

Explanation becomes much more complicated when there are more elements in the array in mixed up fashion. But again due to associativity of XOR operation - We actually end up getting answer.

This has been well explained on geeksforgeeks
geeksforgeeks-dot-org/find-the-element-that-appears-once/

From stack overflow...

def special(lst):
    ones = 0
    twos = 0
    for x in lst:
        twos |= ones & x
        ones ^= x
        not_threes = ~(ones & twos)
        ones &= not_threes
        twos &= not_threes
    return ones



Explanation:

If the problem were this: "one element appears once, all others an even number of times", then the solution would be to XOR the elements. The reason is that x^x = 0, so all the paired elements would vanish leaving only the lonely element. If we tried the same tactic here, we would be left with the XOR of distinct elements, which is not what we want.

Instead, the algorithm above does the following:

ones is the XOR of all elements that have appeared exactly once so far
twos is the XOR of all elements that have appeared exactly twice so far
Each time we take x to be the next element in the array, there are three cases:

if this is the first time x has appeared, it is XORed into ones
if this is the second time x has appeared, it is taken out of ones (by XORing it again) and XORed into twos
if this is the third time x has appeared, it is taken out of ones and twos.
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 x from 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.

Good problem.
we consider the bit separately
v0 is the set whose occurrence time mod 3 = 0
v1 is the set whose occurrence time mod 3 = 1
v2 is the set whose occurrence time mod 3 = 2
we know that each bit must exactly in one state {mod3 = 0, or mod 3 = 1. or mod 3 = 2)
so for a new number, the only thing may happen is that some bit is in vi goto v( (i+1)%3) if both vi and x contains that bit.

#include <iostream>
#include <cmath>
#include <cstdio>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <set>
#include <cstring>
using namespace std;

#define mp make_pair
#define pb push_back

typedef long long LL;

const int MAXN = 333;

int a[ MAXN ]=  {12,1,12,3,12,1,1,5,3,3};

int main(){
	int v0, v1, v2, n = 10;
	v0 =v1 = v2 = 0;
	for(int i = 0; i < n; ++ i) {
		int r0, r1, r2,x=a[i];
		r0 = v0&x; r1=v1&x; r2=v2&x;
		v0 =(v0^r0)|r2;
		v1 =(v1^r1)|(x^r1^r2);
		v2 =(v2^r2)|r1;
	}
	cout << v1 << endl;
	return 0;
}

Superbly explained.
Let me know if you find better explnation than this!
youtube.com/watch?v=mHfvInveXDQ

I have an O(nlogn) answer.
1) Sort the array. O(nlogn)
2) Then for every element keep checking the next element till end. If current element == next Elelement increase the counter. if current Element != next Element then check counter. If counter is zero then return that element. If counter is not zero then make counter zero and proceed. O(n).

space complexity is O(1).

Take an element and take the first bit and divide them into two groups ...
ie all the elements with 1's on one side and 0's on the other side ... now count the left side elements and right side elements ( use the quick sort divide strategy ) and take the side which is not the multipple of 3 now again divide recursively untill you get 3 elements on one side and one elements on the other side .. that one element is the culprit ...

This is the best which i can get ... should try some logical operators

int appearOnce(int arr[], int N)
{
int ones=0, twos=0;
int threes;
for (int i=0; i!=N; ++i){
twos = twos | (ones & arr[i]);
ones = ones ^ arr[i];
threes = ones & twos;
ones &= ~threes;
twos &= ~threes;
}
return ones;
}

#include <iostream>
#include <map>
using namespace std;

int main()
{
int arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3};
map<int, int> m;
pair<int,int> p;

int size = sizeof(arr)/sizeof(arr[0]);

// Insert
for(int i=0; i<size; i++)
{
p.first = arr[i];
p.second = 1;

if ( m.count(arr[i]) > 0)
{
m.at(arr[i])++;
}
else
m.insert(p);
}

// Print
for( map<int, int>::iterator i=m.begin(); i != m.end(); i++)
{
cout << i->first << " " << i->second << endl;
}

return 0;
}

// binary sort : O(log n)
// 1, 1, 1, 2, 3, 3, 3, 12, 12, 12

if array[length] != array[length - 1]
  print arr[length
else
{
for( i=0; i < ( length - 1 ) /3 ; i++)
 if ( arr[i*3] != arr[i*3+2] )
 {
    print arr[i*3];
    break;
  }
}

Use Pivot strategy.If after every trials the pivot is at 0th Index then the number is unique .if number is equal to pivot it will be on left side else on the right side.
Example

12 12 12 3 3 1 2 1 3 1

for 1
1 1 1 12 12 12 3 3 3 2

for 2
2 1 1 1 12 12 12 3 3 3

Thanks for good session.Put a trail on skillgun.com for more interested questions,asked in android developer interview section.

check for more skillgun.com

geekForGeek solution 2 is the best and its generalized solution and works for any k.
---------------source geefForGeek----------------------
Following is another O(n) time complexity and O(1) extra space method suggested by aj. 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.
Let us consider the example array {5, 5, 5, 8}. The 101, 101, 101, 1000
Sum of first bits%3 = (1 + 1 + 1 + 0)%3 = 0;
Sum of second bits%3 = (0 + 0 + 0 + 0)%0 = 0;
Sum of third bits%3 = (1 + 1 + 1 + 0)%3 = 0;
Sum of fourth bits%3 = (1)%3 = 1;
Hence number which appears once is 1000

Take the XOR sum.we will get the sum of unique elements.
Take the sum of original array
As we know each number is repeated 3 times we multiply xor sum with 3
Now missing number is
(Xorsum-sum)/2
Why we have divide the difference because the the non repeated number is taken 3 times in xor sum

float sum;
for(each element)
{
 sum = (float)element * 0.333;
}
float number = take fractional part of sum ;
number *=3;
printf(neartestIntegerOf(number))

Add all the numbers in the array to get 'sum'. Do ((sum) mod 3) to get the number that occurs only once.