I am doing the following programming exercise: Number Zoo Patrol. The statement is:
Background:
You're working in a number zoo, and it seems that one of the numbers has gone missing!
Zoo workers have no idea what number is missing, and are too incompetent to figure it out, so they're hiring you to do it for them.
In case the zoo loses another number, they want your program to work regardless of how many numbers there are in total. Task:
Write a function that takes a shuffled array of unique numbers from 1 to n with one element missing (which can be any number including n). Return this missing number. Examples:
findNumber([1, 3, 4]) should be 2 findNumber([1, 2, 3]) should be 4 findNumber([4, 2, 3]) should be 1
I have difficulties because of it is the first exercise where the time complexity is being tested. There is a test which checks that your algorithm executes in less than one second for huge arrays. The following is the test I am writting about:
import static org.junit.Assert.assertEquals;
import java.util.concurrent.TimeUnit;
import org.junit.Rule;
import org.junit.Test;
import org.junit.rules.Timeout;
public class NumberZooPatrolSampleTest {
@Rule
public Timeout globalTimeout = new Timeout(1, TimeUnit.SECONDS);
@Test
public void testDescriptionExamples() {
assertEquals(2, findMissingNumber(1, 3));
assertEquals(1, findMissingNumber(2, 3, 4));
assertEquals(12, findMissingNumber(13, 11, 10, 3, 2, 1, 4, 5, 6, 9, 7, 8));
}
@Test
public void testPerformanceIsLinear() {
// Solutions with linear runtime should finish in about 200 to 300 ms.
// 1. Generate an array with 999,999 numbers with increasing and
// decreasing values interleaved so sorting algorithms which
// are able detect pre-sorted arrays would still need
// at least loglinear time.
// 2. Find the missing number 100 times.
int[] numbers = generateNumbers(1_000_000, 66_667);
for (int i = 0; i < 249_999; i++) {
int temp = numbers[i * 2];
numbers[i * 2] = numbers[999_997 - i * 2];
numbers[999_997 - i * 2] = temp;
}
for (int i = 0; i < 100; i++)
findMissingNumber(numbers.clone());
}
private static int findMissingNumber(int ... numbers) {
return NumberZooPatrol.findMissingNumber(numbers);
}
private static int[] generateNumbers(int bound, int missingNumber) {
if (missingNumber < 1 || missingNumber > bound)
throw new IllegalArgumentException("Missing number is not in allowed range");
int[] numbers = new int[bound - 1];
int pos = 0;
for (int i = 1; i <= bound; i++)
if (i != missingNumber)
numbers[pos++] = i;
return numbers;
}
}
My first aproach was to compare number by number in the array with the one there should be in that position:
import java.util.*;
import java.util.stream.*;
public class NumberZooPatrol {
public static int findMissingNumber(int[] numbers) {
int[] clone = numbers.clone();
Arrays.sort(clone);
int i = 0;
for(; i < clone.length; i++){
if(clone[i] != i+1){
break;
}
}
return i+1;
}
}
However it does not pass the time complexity test.
Besides I used another approach where we get the difference between the sum of the range and the current array sum:
import java.util.*;
import java.util.stream.*;
public class NumberZooPatrol {
public static int findMissingNumber(int[] numbers) {
if(numbers.length == 0) return 1;
int[] clone = numbers.clone();
Arrays.sort(clone);
int range = IntStream.rangeClosed(1,clone[clone.length-1]).sum();
int sum = IntStream.of(clone).sum();
return range - sum == 0 ? clone.length + 1 : range - sum;
}
}
And it also times out when we execute the time complexity test.
In addition I have read:
- How can I generate a list or array of sequential integers in Java?
- How to sum a list of integers with java streams?
- Make copy of an array
How could we get the missing number from array with an efficient algorithm?‽?
