CareerCup

Since the question doesn't talk about any sorting, i think, [keeping the data along with a counter in a structure] linked list would be a good solution.

method A: hashtable. detect collision. complexity O(n)

method B: sorting, then compare adjacent elements. detect elements which are equal. complexity O(nlogn).

I had a similar question from Expedia:

How would you find the position of the duplicate element(1 duplicate at most) w/ O(1) space. This means you can use static memory but no dynamic allocation like Hash Tables. I didn't solve this problem but mentioned bit manipulation using XOR. Anyone have a clever idea on this?

I think, if you don't want to use dynamic memory, then first sort the array. Then compare two adjacent elements, using xoring function. Means when two elements are equal, then xor result will be zero otherwise 1.

aXORa == 0.
So aXORbXORa = b. XOR is commutative.

So XOR all elements of the array in turn till it becomes zero will give u the repeated number. But i think this can fail sometimes. nybody has a better solution?

If you sort the array, you lose the position of the integer, so sorting isn't allowed.

The solution spontaneously came to me...

1. Calculate the sum from 1 to N, using the series formula.
2. Since there is at most 1 duplicate, you can find the position by searching in either direction, depending on which position you want to find.

The running time is then O(n) and O(1) storage(only original array).

this solution only works if there is additional constraint

size of array = n
all numbers lie with 1- n-1 range.

Am i missing something

Yes. The array is a set of 1 to N.

In Perl:

my %h;
$h{$_}++ for @A;

@dups;
for(keys %h){
push @dups, $_ if $h{$_}>1
}
return @dups;

Use counting sort. It takes O(n)

From the above example

2,3,1,4,5,6,7,7 the sum is 35
but the sum is 35 even for 2,3,1,4,5,6,6,8.. and the repeated
number is 6!
How does just getting the sum help in finding the repeated number?

So, I think Hash which takes O(1) and extra space is the best solution
Second best is to sort and scan the sorted array O(nlogn)

Jack's Expedia question sol:

first pass - xor everything to get duplicate number.
second pass - iterate over array to find position of duplicate number.

so each pass is O(n) and it did not use any extra space.

XOR would work only if ALL the elements in the array are repeated and there is just one number which appears once. XOR-ing would help us find that sole number.

A kind of bit vector like solution, in O(n).
Traverse the array, setting corresponding bit to 1. If the bit already one, then we found our duplicate, if not just keep traversing. Worst case would be if the last element is the repeated one.

But a CATCH is wasted space in creating the bitvector of that size. If range is known, then its great else, we have to make some guesses or give the range of Int.MAX_Value as the size of bit vector

Bit vector sounds expensive since a bit vector supports sequential access, it takes O(n) time to scan.

Mergesort & comparing adjacent duplicates will be O(nlogn). This is expensive as well. O(nlogn) is expensive than O(n). But, this method doesn't need any extra space.

Hash table is the fastest with O(1) retrieval & access times. But a hash table takes extra O(n) space.

So, we need to decide if we want space(mergesort & comparing adjacent duplicates) or time(the lovely hash table).

Convert int array to an Integer array. Add contents of the new array to a TreeSet. when the .add method returns false we have encountered the duplicate.

A simple solution is in O(1).
The sum of first n natural numbers i.e., 1+2+3+...+n if the numbers are in sequence is given by: n*(n+1)/2. So u can apply the above formula i.e., For example:
The below is the given sequence:
2,3,1,4,5,6,7,7.
Now as there are 8 numbers:
8*(8+1)/2 = 36.
Now the sum of the above elements is:35.
So u can easily say that 7 is repeated as sum is 1 less than it should be.