find.c

/*
 * An algorithm for solving the following (classic) hard interview problem:
 *
 * "You are given an array of integers of length n, where each element ranges
 *  from 0 to n - 2, inclusive.  Prove that at least one  duplicate element must
 *  exist, and give an O(n)-time, O(1)-space algorithm for finding some
 *  duplicated element.  You must not modify the array elements during this
 *  process."
 *
 * This problem (reportedly) took CS legend Don Knuth twenty-four hours to solve
 * and I have only met one person (Keith Amling) who could solve it in less time
 * than this.
 *
 */
size_t findArrayDuplicate(int array[], size_t len)
{
        // The "tortoise and hare" step.  We start at the end of the array and try
        // to find an intersection point in the cycle.
        size_t slow = len - 1, fast = len - 1, finder = len -1;

        // Keep advancing 'slow' by one step and 'fast' by two steps until they
        // meet inside the loop.
        do {
                slow = array[slow], fast = array[array[fast]];
        } while (slow != fast);

        // Start up another pointer from the end of the array and march it forward
        // until it hits the pointer inside the array.
        do {
                slow = array[slow], finder = array[finder];
        } while (slow != finder);

        return slow;
}