Imagine we have an immutable array of size N which we know to be filled with integers ranging from 0 to N-2, inclusive.

1. Write a function that checks to see if the array contains a duplicated entry. This function should run as quickly as possible. That is, complete the following function:

   bool contains_duplicate(int* array, int N) {
       // ...
   }

2. Suppose we know that the array contains exactly one duplicated entry and that duplicate appears exactly twice. Find, in constant space and time proportional to N, the duplicated entry. That is, complete the following function:

   int find_unique_duplicate(int* array, int N) { 
       // ...
   }

3. Suppose that we drop the guarantee that the array contains exactly one duplicated entry. Write another find_duplicate function so that it returns one of the duplicated entries. It should still run in constant space and time proportional to N.

   int find_duplicate(int* array, int N) { 
       // ...
   }

Please send your solution (and your resume if you have one ready) to challenge@rapleaf.com.