Loading...
Loading...
Loading...
Students of a class of n type their roll numbers into a lab sheet. Some typed wrong values: zero, negative numbers, repeated numbers or numbers far too large.
Print the smallest positive roll number, starting from 1, that does not appear in the list. Your program should run in O(n) time and use only a few variables besides the array of numbers.
Example 1
Input
5 3 4 -1 1 9
Output
2
1 is present but 2 is not.
Example 2
Input
4 2 1 4 3
Output
5
1 to 4 are all present, so the answer is 5.
Try the problem first. Open one hint at a time.
With n numbers, the answer is always between 1 and n + 1. Numbers below 1 or above n can be ignored.
If you could put each number x from 1 to n at index x - 1, the first index i that does not hold i + 1 gives the answer.
Do it inside the same array: while the number at index i is in range and is not already in its right place, swap it there.
Stop swapping when the target index already holds the same value, or duplicates make the loop run forever.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor