Google Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
15
of 17 vote

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

- Anonymous March 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please explain?

- King@Work March 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

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

- Jon March 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

*bitwise*

- Anonymous March 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- zerg March 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

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

- Anonymous March 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- anon March 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 votes

@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;

}

- siva.sai.2020 March 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- anon March 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ilya March 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
15
of 19 votes

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.

- Rama B March 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

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[15] = {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;
}

- Anonymous March 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous March 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;

}

- mirokuneal March 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Rama B March 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry its still wrong! plz ignore above comment.

- Rama B March 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous March 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous March 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.
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.
This is really a masterpiece.

- BucketRain6 March 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- mirokuneal March 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- pollywog December 22, 2012 | Flag
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.

- Rama B March 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Hatts Off! March 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- IntwPrep October 10, 2013 | Flag
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!
youtube.com/watch?v=mHfvInveXDQ

- Randeep Singh April 05, 2016 | Flag Reply
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).

- insigniya March 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please explain?

- King@Work March 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- insigniya March 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Jon March 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- harini ganesan March 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Siddarth March 30, 2011 | Flag
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

- anon March 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- King@Work March 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- anon March 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- King@Work March 06, 2011 | Flag
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.

- Anonymous March 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous March 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- AttitudeLess March 08, 2011 | Flag
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

- dexter March 08, 2011 | Flag Reply
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);

}

- Manoj March 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You need to sort the array first...

- Manoj March 09, 2011 | Flag
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;
}

}

- Manoj March 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here, no need to sort array

- Manoj March 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

You are welcome!

- Rama B March 12, 2011 | Flag Reply
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?

- AL March 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- kumar January 02, 2012 | Flag Reply
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)..

- abh007 July 27, 2012 | Flag Reply
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);
            Console.ReadLine();
        }
        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;
        }

- Anonymous December 18, 2012 | Flag Reply
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);
            Console.ReadLine();
}
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;
}

- MD December 18, 2012 | Flag Reply
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[32]={0x01};
		for(int i= 1; i<32; i++)
		{
			M[i] = M[0] << i;
		}

		int C[32] = {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;
	}

- BIN December 29, 2013 | Flag Reply
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);

- rahman.kdd July 16, 2014 | Flag Reply
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;

- nikH42 October 29, 2014 | Flag Reply
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;

- nikH42 October 29, 2014 | Flag Reply
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;

- Veena November 04, 2014 | Flag Reply
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

- manikanta December 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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

- Anonymous January 01, 2015 | Flag Reply
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;
}

- for any k, not only 3 June 30, 2015 | Flag Reply
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[0]<>A[1]:
return A[0]
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

- kishorjha94 January 12, 2017 | Flag Reply
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);
}

}

- Somendra Raj June 21, 2017 | Flag Reply
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);
	}

}

- Somendra Raj June 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} - Anonymous January 11, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bullshit

- raut January 11, 2018 | Flag Reply
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[0]);
	printf("The element with single occurrence is %d ",
			getSingle(arr, n));
	return 0;
}

- Gaurav June 18, 2018 | Flag Reply
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[0]);
printf("The element with single occurrence is %d ",
getSingle(arr, n));
return 0;
}

- Gaurav June 18, 2018 | Flag Reply
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!!

- Sanjay March 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- anonymous March 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Upt March 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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[0]^a[1]....^a[n]
solving for y gives
y = (3A - B)/2

- Anonymous March 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous March 30, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

static void Main(string[] args)
{
int[] arr = { 1,4,2,1,4,2,1,2,4,5};
int unique = FindUnique(arr);
Console.WriteLine(unique);
Console.ReadLine();
}
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;
}

- MD December 18, 2012 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More