## Google Interview Question for Software Engineer / Developers

• 8

Comment hidden because of low score. Click to expand.
16
of 18 vote

Add the numbers bitwise mod 3. I guess too many people were just saying "XOR" without understanding properly.

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

Don't think this works if your just saying do (sum of array) mod 3... say the sum is 93... Then (sum of array) mod 3 = 0 which leaves you with possabilities of 3,6,9.... or 94 gives you 1, 4, 7 ect....

Comment hidden because of low score. Click to expand.
0

*bitwise*

Comment hidden because of low score. Click to expand.
0

I think will work if we'll be adding numbers in 3 digit system. For example [2,1,4,5,1,4,2,2,4,1] is equal to [02, 01, 11, 12, 01, 11, 02, 02, 11, 01] in 3 digit system. Adding them "bitwise 3" we'll get: 12 (1=4 mod 3 and 2 = 14 mod 3). (12)3 = (5)10.
Implementation might be tricky however.

Comment hidden because of low score. Click to expand.
2

Not really. From StackOverflow:

``````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``````

Comment hidden because of low score. Click to expand.
0

would u pls give d link of the post on stackoverflow? Or, explain it briefly. Thnx.

Comment hidden because of low score. Click to expand.
4

@anonymous, I compiled and tested your Stackoverflow code and it works fine. This very very good answer.

``````int main()
{
int B[] = {1,1,1,3,3,3,20,4,4,4};
int    ones = 0 ;
int    twos = 0 ;
int not_threes;
int 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;

}``````

Comment hidden because of low score. Click to expand.
0

Another masterpiece of bitwise manipulation-based solution. Seems this is the best answer for this problem. Would would take the courage to explain it for others?
Thanks.

Comment hidden because of low score. Click to expand.
0

i'm pretty sure u don't need "3 digit system" here. simple binary will do

Comment hidden because of low score. Click to expand.
16

Explanation for siva.sai.2020's code.

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.

Comment hidden because of low score. Click to expand.
2

The original 3-based method can also work, this is one implementation. The complexity can be O(nlog{m}) in the worst case where m is the largest element. Actually it's not too bad when the elements are all integers.

``````int main()
{
int B = {712,88,9,33,33,88,712,9,9,88,33,712,2000000000};
int n = 13;
int sum = 0;
int i;
int base = 1;
int one = 0;
for(i = 0; i < n;  i++)
sum += B[i];
while(sum > 0) {
int r = sum % 3;
one += r * base;
for(i = 0; i < n;  i++) {
sum -= B[i] - B[i]/3;
B[i] /= 3;
}
base *= 3;
}
cout << one << endl;
return 0;
}``````

Comment hidden because of low score. Click to expand.
0

The problem is, it could only work when all the elements are positive...

Comment hidden because of low score. Click to expand.
0

Nice try.
However, I don't think siva.sai.2020's code is right.
Somebody try this one. On my machine, it does not work.

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

for (int 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;

}``````

Comment hidden because of low score. Click to expand.
0

@mirokuneal: Thanks a lot for finding this bug.
Well.. I just tried to understand and explain siva's code so i apologize if there is anything wrong in the explanation.

Again after spending few hours, hopefully i have got the correct version.

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

Comment hidden because of low score. Click to expand.
0

Sorry its still wrong! plz ignore above comment.

Comment hidden because of low score. Click to expand.
0

@micro
The code is working. The problem is you have given more than 10 elements, you need to change the value 10 in the for loop

@rama, the original code is working..

Comment hidden because of low score. Click to expand.
0

@rama
I don't know if you fully understand the code, though you gave a very long explanation. You are trying to give wrong answers. The original code by siva is working perfectly. Don't try to give some wrong answers. Both try to change the value (10 to 13) in the for loop, the code will work perfectly...

Comment hidden because of low score. Click to expand.
0

Yes Rama's explanation is wrong. The ones and twos don't hold elements that appeared once or twice. They hold bits that appeared once or twice. Then the algorithm is easy to understand.
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.
This is really a masterpiece.

Comment hidden because of low score. Click to expand.
0

Thanks for explanation. I am so stupid forgeting the length of the array.

Comment hidden because of low score. Click to expand.
0

A simpler explanation: The StackOverflow code came from /questions/5208343/find-a-special-number-in-an-array but it is not explained much there.

Consider the simpler case in which every array element appears twice except for the one unique element. Because x XOR x = 0 and 0 XOR x = x, and XOR is associative and commutative, you can XOR all the elements together, the pairs will all cancel out to 0 and what remains will be the unique element's value.

In this problem the challenge is to find a logical operator, call it FOO that will cancel out three occurrences of the same value. That is, you want an associative and commutative function FOO such that

x FOO x FOO x = 0
and
0 FOO x = x

You can do that with FOO being addition mod 3 as long as you do it separately on each bit. You lose information doing addition mod 3 on numbers bigger than 2.

There is a problem that the result of addition mod 3 might be the value 2 which takes two bits for the result. You have to add the bits mod 3 keeping a two bit accumulator for each bit of the values you are adding. You can do that using two integer variables for the accumulators, one named "ones" for the low order bit and the other named "twos".

The code show here finds the sum of items mod 3 separately for each bit, keeping the low order bit of the results in "ones" and the second bit of the results in "twos". The code uses logical bit operations to do the addition, then sets the two bit results to 0 if they are both 1 (changing 3 to 0 because it is mod 3 addition).

You could probably save a line or two of code by writing an equivalent logical expression for calculating ones and twos as functions of the current value of ones, twos, and item, but each time I tried it I made some silly mistake. Describing it as addition mod two and using the explicit check for clearing the result 3 to 0 makes the code easier to read and less likely to have an error.

Comment hidden because of low score. Click to expand.
2
of 4 vote

Explanation for siva.sai.2020's code.

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.

Comment hidden because of low score. Click to expand.
0

Highly appreciate for such a detailed explanation of an intricate (but, smart) solution!

Comment hidden because of low score. Click to expand.
0

This does not work say when the unique number is obtained from ORing the other numbers.
Example: {1,4,5,1,1,4,4} does not give you the right result

Comment hidden because of low score. Click to expand.
1
of 1 vote

Superbly explained.
Let me know if you find better explnation than this!

Comment hidden because of low score. Click to expand.
0
of 0 vote

Sort the array but in this case time complexity will be n*log(n).

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

Sort the array,
Find i for which
a[i-1] != a[i] != a[i+1]

Comment hidden because of low score. Click to expand.
0

Sounds like that works but don't know if it is most efficient... can't think of better though... this should be a[i-1] != a[i] OR a[i] != a[i+1] as the above only hold true for the middle number of every set of 3 in the array.

Comment hidden because of low score. Click to expand.
0

you can use hash.. with value from 1 to n and key as the the elements of array.

Comment hidden because of low score. Click to expand.
0

I guess they have clearly mentioned do not use any extra memory. So i would with the solution as to sort the array and check if a[i] == a[i+2] and continue if yes, else return the element.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Using memory:
use hash table to store frequency. average complexity O(n), worst case O(n^2).

W/O memory:
sorting, and checking if a[i-1] != a[i+1] for i = 1 to n-2, assuming 0 index array

Comment hidden because of low score. Click to expand.
0

Using hashtable will make the freq table in O(n) plus we have to iterate once more to find the lowest freq elem.
So the worst case will be O(n)+O(n).
Doing merge sort and finding the elem complexity may be lower.

Comment hidden because of low score. Click to expand.
0

@Upt: unless you can define a perfect hashing, how could you convince that worst case time is O(n). What happened if you've a hash function that maps half of the inputs to a single index of hash table. In that case, assume it's a linked list of size O(n). Whenever you'd update the frequency of an element in that list, it'd be O(n) time - that leads O(n^2) worst case complexity for hashing.

Comment hidden because of low score. Click to expand.
0

I agree. I assumed that the hashing is perfect as it is done for the ints in this problem which is not so difficult.

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Do a partition.
1. if number of elements on the both sides are exactly divisible by 3 then Pivoted element is the required number.
2. At least one side of pivoted element will be divisible by 3. So take the other side and perform step 1.

Space Complexity - constant, Time Complexity is o(n),
but array will get destroyed.

Comment hidden because of low score. Click to expand.
0

really...

3,3,3,6,6,6,9

In this case answer should be 9.
But if your pivot is 6 then also it will satisfy ur condition....

Comment hidden because of low score. Click to expand.
0

You have to modify Partition as numbers are duplicated here so in this example 3,3,3,6,6,6,9 if 6 is pivoted element it will return index of last 6.
So 3,3,3,6,6,6 will be one side while 9 will be other side.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Check the solution here on stackoverflow
stackoverflow /questions/2497470/given-an-array-of-integers-where-some-numbers-repeat-1-time-some-numbers-repeat

Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
int B[] = {1,1,1,3,3,3,4,4,4,5,5,5,6,6,6,7,8,8,8,9,9,9};
for(int i=0;i<B.length-2; i=i+3){
if(B[i]!=B[i+1] || B[i+1]!=B[i+2]){
n = B[i];
break;
}
}
if(n==0)
System.out.println("Unique no. - " + B[B.length-1]);
else
System.out.println("Unique no. - " + n);

}

Comment hidden because of low score. Click to expand.
0

You need to sort the array first...

Comment hidden because of low score. Click to expand.
0
of 0 vote

HashMap solution:

int B[] = {1,1,1,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,8,8,8,9,9,9,11,11,11,44,44,44,46};
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
for(int i=0; i<B.length;i++){
if(hm.containsKey(B[i])){
hm.put(B[i], hm.get(B[i])+1);
}else{
hm.put(B[i],1);
}
}
Iterator itr = hm.entrySet().iterator();
while(itr.hasNext()){
Map.Entry pairs = (Map.Entry)itr.next();
if((Integer)pairs.getValue() == 1){
System.out.println("Hash Operation - Unique no. - "+pairs.getKey());
break;
}

}

Comment hidden because of low score. Click to expand.
0

Here, no need to sort array

Comment hidden because of low score. Click to expand.
0
of 0 vote

You are welcome!

Comment hidden because of low score. Click to expand.
0
of 0 vote

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".

@Rama B:
if you consider the sequence 6,2,2,2

After 6 is considered, we have ones=6, twos=0
next comes 2, while doing twos|= ones & x, the and yields 6&2=2 contrary to your statement that the and yields nothing when a new number(this case 2) arrives. Even though the ultimate result comes out to be correct in this sequence also, but looking for an explanation how the correction occurs?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Is the range of numbers in the array known to us ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

No need of sorting.....
....
int SUM=0, a[]={..........}; //
for(i=0;i<SIZE;i++) // SIZE=size of an array
{
SUM+=a[i];
}
for(i=0;i<SIZE;i++)
{
if ( (SUM + 2x)%3==0 && x==a[i] )
return x;
}

complexity=O(n)..

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````static void Main(string[] args)
{
int[] arr = { 1,4,2,1,4,2,1,2,4,5};
int unique = FindUnique(arr);
Console.WriteLine(unique);
}
public static int FindUnique(int[] arr)
{
int once = 0; int twice = 0; int Threes; int x = 0;

for (int i = 0; i < 10; i++)
{
x = arr[i];
twice |= once & x; //add it to twice if it exists in once
once ^= x; //it exists in once, remove it, otherwise, add it
Threes = once & twice;  //if x is in once and twice, add it to Threes.
// and thus
once &= ~Threes; //remove x from once
twice &= ~Threes; //remove x from twice
}
return once;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````static void Main(string[] args)
{
int[] arr = { 1,4,2,1,4,2,1,2,4,5};
int unique = FindUnique(arr);
Console.WriteLine(unique);
}
public static int FindUnique(int[] arr)
{
int once = 0; int twice = 0; int Threes; int x = 0;

for (int i = 0; i < 10; i++)
{
x = arr[i];
twice |= once & x;             //add it to twice if it exists in once
once ^= x;                        //if x exists in once, remove it, otherwise, add it
Threes = once & twice;    //if x exists in once and twice, add it to Threes.
once &= ~Threes;            //remove x from once
twice &= ~Threes;           //remove x from twice
}
return once;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

bitwise and easier to be understandable

``````int findIntOnceOfThrees(int* A, int n)
{
int M={0x01};
for(int i= 1; i<32; i++)
{
M[i] = M << i;
}

int C = {0};
for(int i=0; i<n; i++)
{
for(int j=0; j<32; j++)
{
if (A[i] & M[j])
{
C[j] = (C[j]+1)%3;
}
}
}
int ret = 0;
for(int i=0; i<32; i++)
{
if (C[i])
{
ret |= M[i];
}
}
return ret;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I've jus ACed the same problem in leetcode.
Here is my code:

``````public class Solution {
public int singleNumber(int[] A) {
if(A.length <1) return 0;
int result = 0;
int count = 0;      //adding binary digits at the same place
for(int j = 0; j < 32; j++){
for(int i = 0; i < A.length; i++){
if(((A[i] >> j) & 1) == 1)
count++;
}
result |= ((count % 3) << j);   //this gives binary digit of the single one at Jth place.
count = 0;
}
return result;
}``````

}
Basically used the top answer strategy, adding numbers up bitwise, mod 3 get the bit for the single one.
Time complexity O(n), space complexity O(1);

Comment hidden because of low score. Click to expand.
0
of 0 vote

Algo:-
new element - > xor with 'ones'
element repeated twice - > remove from 'ones' and xor with 'twos'
element repeated thrice -> remove from both 'ones' and 'twos'
return ones

code:-
public int singleNumber(int[] A) {
int ones = 0, twos = 0;
for(int i = 0; i < A.length; i++){
ones = (ones ^ A[i]) & ~twos;
twos = (twos ^ A[i]) & ~ones;
}
return ones;

Comment hidden because of low score. Click to expand.
0
of 0 vote

Algo:-
new element - > xor with 'ones'
element repeated twice - > remove from 'ones' and xor with 'twos'
element repeated thrice -> remove from 'twos'
return ones

code:-

``````public int singleNumber(int[] A) {
int ones = 0, twos = 0;
for(int i = 0; i < A.length; i++){
ones = (ones ^ A[i]) & ~twos;
twos = (twos ^ A[i]) & ~ones;
}
return ones;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I found it pretty complicated to understand the above logic when elements were scattered eg 4,3,4,3,4. I found the solution 2 by geeksforgeeks simpler to understand for people like me. "geeksforgeeks.org/find-the-element-that-appears-once/"

Explanation directly from geekForGeeks
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;

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int find(int[] A) {
int[] cnt = new int;

for(int x : A) {
for(int i = 0; i < 32; i++) {
cnt[i] += (x >> i) & 1;
}
}

int res = 0;
for(int i = 0; i < 32; i++) {
res += (cnt[i] % 3 == 0 ? 0 : 1) << i;
}

return res;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int get_uniq(const vector<int> &v, size_t k)
{
size_t s = sizeof(int) * 8;
vector<int> bits(s);

for (const int el: v)
{
for (size_t j = 0; j < s; ++j)
{
bits[j] += (el & (1 << j)) >> j;
}
}

int res = 0;
for (size_t j = 0; j < s; ++j)
{
if (bits[j] % k == 1)
{
res |= (1 << j);
}
}
return res;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

class Solution:
def occurs(self,A):
A.sort()
if len(A)>1:
if A<>A:
return A
f=0
for i in xrange(1,len(A)-1):
f=1
if A[i-1]<>A[i] and A[i]<>A[i+1]:
return A[i]
if f==1:
if A[len(A)-2]<>A[len(A)-1]:
return A[len(A)-1]
return -1

ss=Solution()
print ss.occurs([2, 1, 2, 3, 12, 1, 1, 2, 3, 3])

output 12

Comment hidden because of low score. Click to expand.
0
of 0 vote

package Algorithm.Bit;

public class ElementAppearsOnce {

static int getInteger(int arr[], int n){
int result = 0;
int x, sum;
for(int i=0;i<32;i++){
sum = 0;
x = (1<<i);
for(int j=0;j<n;j++){
if((arr[j] & x) ==0)
sum++;
}
if(sum%3==0)
result = result|x;
}

return result;
}

public static void main(String args[]){
int arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7};
int n = arr.length;
int res = getInteger(arr, n);
System.out.println(res);
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package Algorithm.Bit;

public class ElementAppearsOnce {

static int getInteger(int arr[], int n){
int result = 0;
int x, sum;
for(int i=0;i<32;i++){
sum = 0;
x = (1<<i);
for(int j=0;j<n;j++){
if((arr[j] & x) ==0)
sum++;
}
if(sum%3==0)
result = result|x;
}

return result;
}

public static void main(String args[]){
int arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7};
int n = arr.length;
int res = getInteger(arr, n);
System.out.println(res);
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
Comment hidden because of low score. Click to expand.
0
of 0 vote

bullshit

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <stdio.h>
#define INT_SIZE 32

int 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;
}

// Driver program to test above function
int main()
{
int arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7};
int n = sizeof(arr) / sizeof(arr);
printf("The element with single occurrence is %d ",
getSingle(arr, n));
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#define INT_SIZE 32

int 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;
}

// Driver program to test above function
int main()
{
int arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7};
int n = sizeof(arr) / sizeof(arr);
printf("The element with single occurrence is %d ",
getSingle(arr, n));
return 0;
}

Comment hidden because of low score. Click to expand.
-1
of 3 vote

1. Brute Force - O(n^2) - No extra memory
2. Sort - O(nlogn) - No extra Memory
3. Hash - O(n) - Extra Memory
4. XOR - O(n) - No Extra Memory

for eg. [2,1,4,5,1,4,2,2,4,1]=>5
steps: 1. XOR all elements, that will give unique sum say X
Unique Sum,X= 2^1^4^5^1^4^2^2^4^1 = 1+2+4+5=12
2. Calculate total sum, Y = 26
3. Ans Z = (Y-(X*3))/2= (26-(12*3))/2= 5

enjoy!!

Comment hidden because of low score. Click to expand.
0

Smart people work with XOR stuff for this type of problems without knowing properly what the operation does indeed!

XORing 3, 6 and 9 does NOT result in 3 + 6 + 9 = 18, it gives (11) ^ (110) ^ (1001) = (1100) = 12. Now, ask yourself why it gives 12, NOT 18? Then you'd learn what XOR operation does indeed.

Comment hidden because of low score. Click to expand.
0

I got what the XOR does but I am interested that how this equation (Y-(X*3))/2 is derived.

Comment hidden because of low score. Click to expand.
0

Let x be sum of all numbers occurring 3 times and y be no which is occurring once, A be sum of all unique nos in the array and B be sum of all nos in the array, then following conditions hold good

3x + y = B
x + y = A (You get A by XOR all elements)

A = a^a....^a[n]
solving for y gives
y = (3A - B)/2

Comment hidden because of low score. Click to expand.
0

steps: 1. XOR all elements, that will give unique sum say X
Unique Sum,X= 2^1^4^5^1^4^2^2^4^1 = 1^2^4^5=12 ????

I can not get it. It IS NOT SUM!!

Comment hidden because of low score. Click to expand.
0

static void Main(string[] args)
{
int[] arr = { 1,4,2,1,4,2,1,2,4,5};
int unique = FindUnique(arr);
Console.WriteLine(unique);
}
public static int FindUnique(int[] arr)
{
int once = 0; int twice = 0; int Threes; int x = 0;

for (int i = 0; i < 10; i++)
{
x = arr[i];
twice |= once & x; //add it to twice if it exists in once
once ^= x; //it exists in once, remove it, otherwise, add it
Threes = once & twice; //if x is in once and twice, add it to Threes.
// and thus
once &= ~Threes; //remove x from once
twice &= ~Threes; //remove x from twice
}
return once;
}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.