Puzzle : finding out repeated element in an Array

Question

Size of an array is n.All elements in the array are distinct in the range of [0 , n-1] except two elements.Find out repeated element without using extra temporary array with constant time complexity.

I tried with o(n) like this.

   a[]={1,0,0,2,3};
    b[]={-1,-1,-1,-1,-1};
    i=0;
    int required;
    while(i<n)
    {
      b[a[i]]++;
      if(b[a[i]==1)
        required=a[i];
    }
    print required;

If there is no constraint on range of numbers i.e allowing out of range also.Is it possible get o(n) solution without temporary array.

Answer 1

1. Look what is first and last number
2. Calculate SUM(1) of array elements without duplicate (like you know that sum of 1...5 = 1+2+3+4+5 = 15. Call it SUM(1)). As AaronMcSmooth pointed out, the formula is Sum(1, n) = (n+1)n/2.
3. Calculate SUM(2) of the elements in array that is given to you.
4. Subtract SUM(2) - SUM(1). Whoa! The result is the duplicate number (like if a given array is 1, 2, 3, 4, 5, 3, the SUM(2) will be 18. 18 - 15 = 3. So 3 is a duplicate).

Good luck coding!

Answer 2

Lazy solution: Put the elements to java.util.Set one by one by add(E) until getting add(E)==false.

Sorry no constant-time. HashMap:O(N), TreeSet:O(lgN * N).

Answer 3

Pick two distinct random indexes. If the array values at those indexes are the same, return true.

This operates in constant time. As a bonus, you get the right answer with probability 2/n * 1/(n-1).

Answer 4

Build a lookup table. Lookup. Done.

Non-temporary array solution:

Build lookup into gate array hardware, invoke.

Answer 5

XOR all the elements together, then XOR the result with XOR([0..n-1]).

This gives you missing XOR repeat; since missing!=repeat, at least one bit is set in missing XOR repeat.

Pick one of those set bits. Iterate over all the elements again, and only XOR elements with that bit set. Then iterate from 1 to n-1 and XOR those numbers that have that bit set.

Now, the value is either the repeated value or the missing value. Scan the elements for that value. If you find it, it's the repeated element. Otherwise, it's the missing value so XOR it with missing XOR repeat.

Answer 6

O(n) without the temp array.

a[]={1,0,0,2,3};
i=0;
int required;
while(i<n)
{
  a[a[i] % n] += n;
  if(a[a[i] % n] >= 2 * n)
    required = a[i] % n;
}
print required;

(Assuming of course that n < MAX_INT - 2n)

Answer 7

The best I can do is O(n log n) in time and O(1) in space:

The basic idea is to perform a binary search of the values 0 through n-1, passing over the whole array of n elements at each step.

1. Initially, let i=0, j=n-1 and k=(i+j)/2.
2. On each run through the array, sum the elements whose values are in the range i to k, and count the number of elements in this range.
3. If the sum is equal to (k-i)*(k-i+1)/2 + i*(k-i+1), then the range i through k has neither the duplicate nor the omitted value. If the count of elements is less than k-i+1, then the range has the omitted value but not the duplicate. In either case, replace i by k+1 and k by the new value of (i+j)/2.
4. Else, replace j by k and k by the new value of (i+j)/2.
5. If i!=j, goto 2.

The algorithm terminates with i==j and both equal to the duplicate element.

(Note: I edited this to simplify it. The old version could have found either the duplicate or the omitted element, and had to use Vlad's difference trick to find the duplicate if the initial search turned up the omitted value instead.)

Answer 8

Based on @sje's answer. Worst case is 2 passes through the array, no additional storage, non destructive.

O(n) without the temp array.

a[]={1,0,0,2,3};
i=0;
int required;
while (a[a[i] % n] < n)    
   a[a[i++] % n] += n;

required = a[i] % n;
while (i-->0)
   a[a[i]%n]-=n;

print required;

(Assuming of course that n < MAX_INT/2)