CareerCup

This was a hard problem until Khoa mentioned thinking about the numbers on a binary level. Since each number XOR'ed by itself will clear it's set bits, you can go through the array XORing each number and end up with the number without a pair.

Consider the example:
2,3,2,4,3

0010 // 2
0011 // 3
---- // XOR'ed
0001 // result
0010 // 2
---- // XOR'ed
0011 // result: 3 (the odd number so far)
0100 // 4
---- // XOR'ed
0111 // result
0011 // 3
---- // XOR'ed
0100 // result 4 (The odd number in the sequence)

This can be done in O (N LOG N).
You first sort O(N LOG N) then scan it O(N).

This can also be done in O (N) time with O(N) memory.
Radix sort O( N Log N) then scan it O(N).

Is it possible to do this in linear time without using extra memory?

I mean Radix Sort O(N).

Shouldn't { 2*n*(n+1)/2 - Array Sum } work ?

Yes! It would work but you're assuming that the array is a continuous sequence. What if it's not a continuous sequence of integers?

It can be done in O(n) without extra storage.

It can be done in n without extra storage.

use counting sort u can do it in o(n) time

Let MIN be smallest and MAX be largest element in array A. Counting Sort needs to create an extra array[MAX-MIN]. This algorithm would run in O(N) but takes too much memory.
A friend of mine gave me a very clever solution today. We need to compare the numbers in the binary level.

Assume that this is an array of integers (32 bits). This algorithm would run in
O(N * 32) worse case.

1. For each element in the Array, if the least significant bit is 1, increment a counter. Also keep track of the Lastest_Index that has the LSB equals 1.

2. If the counter is 1, then you know that the odd occuring number is at location Latest_Index.

3. Perform Step 1 but check the Next Bit.

This is a very clever solution.

I can see many bugs in this algorithm.

Using Hash table, and the number as key. You will be able to find the number without dup. O(N) time and O(N) memory

Using Hash table, and the number as key. You will be able to find the number without dup. O(N) time and O(N) memory

Hi Jack :o)

O(n) seems like a good answer given the time constraint in the interview.

Hi Jack :o]

O(n) seems like a good answer given the time constraint in the interview.

Hi Jack

O(n) seems like a good answer given the time constraint in the interview.

I would do a modified version of quick sort.

When you partition, if both partitions have equal
number of elements, then the pivot is occuring odd times.

Otherwise, go for partitioning the side with odd number of
elements.

This like selection sort has O(n) has complexity

khoa, does your solution work? what if the non-recurring number is 0?

No! My solution doesn't work. The XOR solution is the correct solution.

tks. I'd like to add that another application of this XOR solution is in GUI applications. When you are drawing a line, e.g., when you press the mouse and move around, use XOR bgcolor with current draw color once to draw a temporary line, and twice to cancel the temporary drawing. this would eliminate the need to refresh the entire dirty rectangle which may include a lot of other drawings.

there is another clever app of XOR. can anyone think of it?

How about this..

Create a set of nine buckets 1 to 9. Let each bucket act has a head to a linked list.

As each number is scanned, store it in the bucket according to its first digit. If you encounter a number that already exists in the bucket then remove it from the bucket.

At the end, when you scan the buckets, you will have a number that has not been repeated.

Does this sound like a good solution? I guess it would be O(n) too.

Joel,

That is a good solution, but would entail using way too much space and eventhough the asymptotic bound will be O(n), the constant factors will be too high then the XOR solution

Well done TheChronoTrigger (XOR solution) and Peter (Modified QuickSort Solution) !!

for the modified quick sort algorithm:

i dont see why the pivot will be the odd element, if the no. of elements in the left and right partitions are equal..

eg: consider 8 as the pivot element

4, 3, 6, 3, 4 ,7, 6, 7, 8, 9, 9

For modified quicksort, if the pivot is a duplicate, then the split could still be balanced and would be ambiguous.

Counterexample:

Unique element on the left
odd + odd = even

Other duplicates on the right
even + even = even

Hence, this conflicts with the case in which the pivot is the unique element.

You could prove that the XOR solution works by associativity(assuming commutativity):

(a XOR b) XOR c = a XOR (b XOR c)?

Suppose
a=01
b=10
c=11

Left side is 11 XOR 11 = 00
Right side is 01 XOR 01 = 00.

With associativity, you could show that by distancing a1 and a2, the solution still holds.

A little tweak should solve what Jack pointed out regarding duplicate pivot when using modified quicksort, which is to throw away the other duplicate pivot when doing randomized partition.

You can simply start XOR each of the values in the array. The final value that remains will be the integer that is present only once in the array. This will work since XOR is associative and symmtrical.

The solution proposed by khoa was a very clever one. Xoring would work perfectly find and is a wonderful solution.

How will u find the other duplicate in randomized quicksort??
It will totally spoil the complexity. The XOR solution is the best solution.

Xor is good

hats off to TheChronoTrigger

In my view we need not sort the array.
1. Start from first element and find its duplicate against rest of elements ahead of it in array.
2. If found continue else break.
3. Keep moving ahead unless you find the number.

Since they mention just integers does the solution take into account stuf like -1,-2 etc??

Go on XORing the numbers. Since n XOR n will be zero, all the duplicates will cancel each other. The value in the end will be the one that doesnt have a duplicate. O(n) time with no extra space.

XOR is the way to go. XOR all the numbers and the output will be the no missing. Take just 3 nos. 2,2,3 when u XOR 2 with itself it will give 0 and XOR of a no with 0 is the number itself. Hence XORing all the nos. will give the missing no.

XOR all the numbers ..
..
The duplicates cancel each other out and give 0 ..
Single element XOR 0 gives the element

Sorting is *not* needed.
Here is a one-liner in Python:

>>> a = 2*range(10)
>>> a.append(77777)
>>> random.shuffle(a)
>>> a
[1, 9, 3, 2, 5, 6, 7, 7, 9, 77777, 0, 8, 1, 3, 8, 4, 0, 2, 4, 5, 6]
>>> reduce(lambda x,y: x^y,a)
77777

but isnt XOR a bitwise operation..and inputs are 0 and 1...here its a huge array of +ve integers...????

public class Test{


public static void main(String args[]){

int a[] = {600,100,200,300,400,300,400,500,600,100,200};

int value = 0;

for (int i=0;i<a.length;i++){
value = value ^ a[i] ;

}

System.out.println("Value is "+value);

}

}

//Output is 500

A bitwise exclusive or takes two bit patterns of equal length and performs the logical XOR operation on each pair of corresponding bits. The result in each position is 1 if the two bits are different, and 0 if they are the same. For example:

0101
XOR 0011
= 0110
Hope it helps

8x's answer clearly says that XOR is THE answer! just try the python one-liner you'll get to know the logic...

Well the XOR solution works for sure , I am just a bit curious , suppose if there are numbers that are present odd number of times (apart from the one that is not duplicated) , then the XOR solution might not work , and is there a way of solving that problem ,( I suppose that duplicate does not mean the number being replicated even number of times.)

XOR solution wont work if the odd occurring number is 0. isn't it?

For ex: 2, 6, 4 ,4, 0, 2, -1,6,-1

XOR solution wont work if the odd occurring number is 0. isn't it?

For ex: 2, 6, 4 ,4, 0, 2, -1,6,-1

what will happen if my array is = {1,2}
I dont think xor will work here..
{1,2} should give me error.But doing XOR will not give me any error.
please correct me if I am wrong.