No. 59 - Duplications in Arrays

Questions: All numbers in an array with length n+1 are in range from 1 to n, so there is at least one duplication in the array. How to find any a duplication? Please don't modify the input array.

Analysis: The simple solution is to utilize hash tables. When scanning the array, array elements are inserted into the hash table one by one. In this way, it's easy to find a duplication with the hash table, which costs O(n) space.

Let's try not to employ extra space. Why there are duplications in the array? If there are no duplications, the count of numbers ranging from 1 to n is n. Since the array contains more than n numbers, there should be duplications. It looks like it's important to count numbers in ranges.

Let's divide numbers from 1 to n into two ranges, split with the number in the middle (denoted as m), and then count the numbers of the two subranges. If the count of numbers from 1 to m is greater than m, the duplication is in the range from 1 to m. Otherwise, there should be at least one duplication in the range from m+1 to n. And then we continue the recursive process until we find the duplication.

The Java code is listed below:

static int countRange(int[] numbers, int start, int end)

{

    int count = 0;

    for(int i = 0; i < numbers.length; i++)

        if(numbers[i] >= start && numbers[i] <= end)

            ++count;

    return count;

}

static int getDuplication(int[] numbers)

{

    int start = 1;

    int end = numbers.length;

    while(end >= start)

        int middle = ((end - start) >> 1) + start;

        int count = countRange(numbers, start, middle);

        if(end == start) {

            if(count > 1)

                return start;

            else

        break;

    }

    if(count > (middle - start + 1))

        end = middle;

    else

        start = middle + 1;

    }

    return -1;

}

The code with unit tests is shared at http://ideone.com/lhV22m.

More coding interview questions are discussed in my book< Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this article in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact the author via zhedahht@gmail.com . Thanks.