algorithm - Array Homework Question

Question

You are given an array with integers between 1 and 1,000,000. One integer is in the array twice. How can you determine which one? Can you think of a way to do it using little extra memory.

Algo:

• Solution 1:
  1. Have a hash table
  2. Iterate through array and store its elements in hash table
  3. As soon as you find an element which is already in hash table, it is the dup element
  Pros:
  • It runs in O(n) time and with only 1 pass
  Cons:
  • It uses O(n) extra memory

Solution2:

1. Sort the array using merge sort (O(nlogn) time)
2. Parse again and if you see a element twice you got the dup.

Pros:
• it doesn't use extra memory

Cons:

• Running time is greater than O(n)

Can you guys think of any better solution?

question from:https://stackoverflow.com/questions/1151318/array-homework-question

Answer 1

The question is a little ambiguous; when the request is "which one," does it mean return the value that is duplicated, or the position in the sequence of the duplicated one? If the former, any of the following three solutions will work; if it is the latter, the first is the only that will help.

Solution #1: assumes array is immutable

Build a bitmap; set the nth bit as you iterate through the array. If the bit is already set, you've found a duplicate. It runs on linear time, and will work for any size array.

The bitmap would be created with as many bits as there are possible values in the array. As you iterate through the array, you check the nth bit in the array. If it is set, you've found your duplicate. If it isn't, then set it. (Logic for doing this can be seen in the pseudo-code in this Wikipedia entry on Bit arrays or use the System.Collections.BitArray class.)

Solution #2: assumes array is mutable

Sort the array, and then do a linear search until the current value equals the previous value. Uses the least memory of all. Bonus points for altering the sort algorithm to detect the duplicate during a comparison operation and terminating early.

Solution #3: (assumes array length = 1,000,001)

1. Sum all of the integers in the array.
2. From that, subtract the sum of the integers 1 through 1,000,000 inclusive.
3. What's left will be your duplicated value.

This take almost no extra memory, can be done in one pass if you calculate the sums at the same time.

The disadvantage is that you need to do the entire loop to find the answer.

The advantages are simplicity, and a high probability it will in fact run faster than the other solutions.