Arrays/Java/Finding Duplicates

Questions

Finding one duplicate

Question C-3.17) A is an array of size n>=2 containing integers from 1 to n-1, inclusive, one of which is repeated. Describe an algorithm for finding the integer in A that is repeated.

A special case of this question is when array A is sorted, since then we know that each array element should correspond to its own index plus 1, and we can do a binary search to locate the array index that does not match the criteria. In this case, the runtime is O(log n).

Finding multiple duplicates

Question C-3.18) Let B be an array of size n>=6 containing integers from 1 to n-5, inclusive. Five of the integers are repeated. Describe an algorithm for finding the five integers in B that are repeated.

Solution approach

There are a few different solution approaches.

In the single element duplicate case:

Sorted array, single element duplicate:

• O(log n) - each element's index correlates to the element's value, so use a binary search to find the location where the correlation is off

Unsorted array, single element duplicate:

• O(n) - to iterate through each element and check for membership in a set; if not a member then add it, otherwise it's a duplicate element; subsequent O(1) lookups in hash table.
• O(n log n) - to sort the array, then O(log n) to find duplicates, sequentially, using binary search

In the multi-element duplicate case: