Want a job working on mongoDB? Your first online interview is in this post

The easy part is that we know that if x and y are the missing and duplicate indices form vector V then we have:

    |x-y| = |sum(V) - (N*(N-1))/2|

Compare the sum with the expected sum. Compare the sum of squares with the expected sum of squares.

Two equations, just solve them. I wrote the final equations in the blog comments.

  def find_missing_duplicate(seq)
    sum = seq.reduce(0, :+)
    corrsum = (seq.size*(seq.size+1))/2

    sumpow = seq.map{|i| i*i}.reduce(0, :+)
    corrsumpow = (1..seq.size).map{|i| i*i}.reduce(0, :+)
    
    diff = sum - corrsum
    diffpow = sumpow - corrsumpow
   
    seq.each do |i|
      miss = i-diff
      if (i*i - miss*miss == diffpow)
        return miss, i
      end
    end 
  end

  MIN_N = 2
  MAX_N = 1000

  (MIN_N..MAX_N).each do |n|
    duplicate = missing = rand(n)+1
    duplicate = rand(n)+1 while duplicate == missing
    seq = (1..n).map{|i| i}
    seq[missing-1]=duplicate

    miss, dup = find_missing_duplicate(seq)
    if !(miss == missing and dup == duplicate)
      $stderr.puts "ERROR: expecting #{missing}:#{duplicate} got #{miss}:#{dup}"
    end
  end

    package main

    import (
        "fmt"
    )

    func main() {
        // a is the sample array
        a := []int{0,2, 3, 3}

        // Reorder values such that a[i] == i when i is not the missing value.
        for i := 0; i < len(a); i++ {
            j := a[i]
            k := a[j]
            a[j] = j
            a[i] = k
        }

        // Look for a[i] != i
        for i := 0; i < len(a); i++ {
            if a[i] != i {
                fmt.Println("missing:", i, "duplicate:", a[i])
                break
            }
        }
    }

I haven't worked out the details or explicitly proven that this will work, but I think the following algorithm should do it:

1) Count up the number of even numbers in the list and compare it to the number we'd expect if the list was "right". This will either be correct (in which case both missing and dupe are even, or both are odd), high (the missing one was odd and the duped one was even), or low (the missing one was even and the duped one was odd).

If high or low, we've just pinned down the last binary digit of each of the numbers.

If even, the digit remains in an unknown state.

2) Slice off the last digit.

3) Repeat 1) and 2) for all 64 bits.

4) Now we have our missing number in the form 001001x1...xx01x (64 bits worth), where the x's represent digits where the missing number's digit matches the duped one.

5) We know the difference between the missing and duped numbers because of the triangular sum formula N(N+1)/2. Use that to solve for the xs in the missing number. That equation will not be possible to solve in general, but the statement of the problem here assures us that it will have a solution; further, I'm pretty sure that as long as the duped and missing numbers are not equal, that solution will be unique (EDIT: it's not, and this method doesn't work at all :P ).

Maybe I'm missing something, though? Haven't thought this through too deeply...

Called the missing number m, duplicate d.

The main idea is to find m+d and m-d. Then it’s trivial to find m and d.

1) Find n XOR d:

   X_array = 1;
   I_array = 1;

   for (i=2..N)

      X_array = X_array XOR A[i]; I_array = I_array XOR i;

   endfor

2) Find m – d

It will be a little bit more complicated. The idea is to get the sum of (1..N) subtract the sum of our array. But we have to be careful not to over or underflow the result.

   Diff = 0;

   i = j = 0; // i index I, j index A

   while (i < N) && (j < N)

     if (Diff + i < N-1)

         Diff = Diff + i;

         i++; //consume one in I

     else

         Diff = Diff – A[j];

         j++; // consume one in J

     endif

   end

3) So we have (m XOR d) and m – d. Also, note that m XOR d is basically m + d without the carry bit so it will be trivial to get m and d.

running time : 3 N <- can be squeeze to 2N if merge the two logic

space : O(1)

  for x in [0..2^64)
    count = 0
    for i in [0..N)
      count += (array[i] == x)
    }
    number[count] = x     // 0 <= count <= 2 
  }
  print "missing: ", number[0]," duplicate: ", number[2]

m is missing,d is duplicate. I is 1..N, A is input.

Step 1: Compute m XOR d by XOR all values of A and I together. let say x = m XOR d. Then x must has at least one 1 bit (or else m == d). Call the bit p. So now we can separate A into two list A0 are those with bit p == 0 and A1 are those with bit p == 1. So we have separated m and d into two different list.

Step 2: Iterate through I, maintain two number x0 and x1 as the results of XOR operations of those elements with p bit == 0 and == 1 respectively. Do the same for A to get a0 and a1. Then we know that m is either a0 XOR x0 or a1 XOR x1. One more linear test in A to confirm the missing element m.

In the end, the running time can be squeezed into 2 N. space = O(1).

Create a Bloom filter on your array, one element at a time. For each element, test whether it is present in the set, and then add it to the set. By testing whether the element is already in the set, you identify the duplicated value. After creating your complete Bloom filter, then test integers 1 to N to see which is not in the set; this is your missing value. I believe this should be constant space and linear time.

Above I said "probably" because there are false positives (though not false negatives).