Q.An array contains n numbers ranging from 0 to n-2. There is exactly one number duplicated in
the array. How do you find the duplicated number? For example, if an array with length 5 contains numbers {0, 2,
1, 3, 2}, the duplicated number is 2.
www.cinterviews.com appreciates your contribution please mail us the questions you have to cinterviews.blogspot.com@gmail.com so that it will be useful to our job search community
A.Suppose that the duplicated number in the array is m. The sum of all numbers in the array, denoted as
sum1, should be the result of 0+1+...+(n-2)+m. It is not difficult to get the sum result of 0+1+...+(n-2),
which is denoted as sum2. The duplicated number m is the difference between sum1 and sum2. The
corresponding code in Java is shown in Listing 3-2.
Listing 3-2. Java Code to Get a Duplicated Number in an Array
Test Cases:
Listing 3-2. Java Code to Get a Duplicated Number in an Array
int duplicate(int numbers[]) {
int length = numbers.length;
int sum1 = 0;
for(int i = 0; i < length; ++i) {
if(numbers[i] < 0 || numbers[i] > length - 2)
throw new IllegalArgumentException("Invalid numbers.");
sum1 += numbers[i];
} int sum2 = ((length - 1) * (length - 2)) >> 1;
return sum1 - sum2;
}
Test Cases:
-
Normal case: an array with size n has a duplication
-
Boundary case: an array {0, 0} with size 2
-
Some numbers are out of the range of 0 to n-2 in an array of size n
Q. 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. A.A naive solution for this problem is to sort the input array because it is easy to find duplication in a sorted array. As we know, it costs O(nlogn) time to sort an array with n elements. Another solution is the utilization of a hash set. All numbers in the input array are scanned sequentially. When a number is scanned, we check whether it is already in the hash set. If it is, it is a duplicated number. Otherwise, it is inserted into the set. The data structure HashSet in Java is quite helpful in solving this problem. Even though this solution is simple and intuitive, it has costs: O(n) auxiliary memory to accommodate a hash set. Let’s explore a better solution that only needs O(1) memory. 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.
With an understanding of the detailed step-by-step analysis, it is time to implement code. Sample code in Java is shown in Listing 3-3.
Listing 3-3. Java Code to Get a Duplicated Number in an Array
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.");
}
Test Cases:
-
Normal cases: an array with size n has one or more duplicated numbers
-
Boundary cases: the array {0, 0} with size 2
-
Some numbers are out of the range from 0 to n-1 in an array of size n
-
No duplication in the array
