An array contains n numbers ranging from 0 to n-1. There are some numbers duplicated in the

array. It is not clear how many numbers are duplicated or how many times a number gets duplicated. How do you

find a duplicated number in the array? For example, if an array of length 7 contains the numbers {2, 3, 1, 0, 2, 5,

3}, the implemented function (or method) should return either 2 or 3.

Indexes in an array with length n are in the range 0 to n-1. If there were no duplication in the n

numbers ranging from 0 to n-1, we could rearrange them in sorted order, locating the number i as the ith

number. Since there are duplicate numbers in the array, some locations are occupied by multiple

numbers, but some locations are vacant.

Now let’s rearrange the input array. All numbers are scanned one by one. When the ith number is

visited, first it checks whether the value (denoted as m) is equal to i. If it is, we continue to scan the next

number. Otherwise, we compare it with the mth number. If the ith number equals the mth number,

duplication has been found. If not, we locate the number m in its correct place, swapping it with the mth

number. We continue to scan, compare, and swap until a duplicated number is found.

Take the array {2, 3, 1, 0, 2, 5, 3} as an example. The first number 2 does not equal its index 0, so it is

swapped with the number with index 2. The array becomes {1, 3, 2, 0, 2, 5, 3}. The first number after

swapping is 1, which does not equal its index 0, so two elements in the array are swapped again and the

array becomes {3, 1, 2, 0, 2, 5, 3}. It continues to swap since the first number is still not 0. The array is {0,

1, 2, 3, 2, 5, 3} after swapping the first number and the number with index 3. Finally, the first number

becomes 0.

Let’s move on to scan the next numbers. Because the following three numbers, 1, 2 and 3, are all

equal to their indexes, no swaps are necessary for them. The following number, 2, is not the same as its

index, so we check whether it is the same as the number with index 2. Duplication is found since the

number with index 2 is also 2.

int duplicate(int numbers[]) { int length = numbers.length; for(int i = 0; i < length; ++i) { if(numbers[i] < 0 || numbers[i] > length - 1) throw new IllegalArgumentException("Invalid numbers."); } for(int i = 0; i < length; ++i) { while(numbers[i] != i) { if(numbers[i] == numbers[numbers[i]]) { return numbers[i]; } // swap numbers[i] and numbers[numbers[i]] int temp = numbers[i]; numbers[i] = numbers[temp]; numbers[temp] = temp; } } throw new IllegalArgumentException("No duplications."); }