Loading...
Loading...
Loading...
Students hand in their assignments in random order, and the teacher writes down each roll number as it arrives. Some students hand in twice, and roll numbers in this system can be negative.
Find the longest set of roll numbers that form a run of consecutive whole numbers, such as 4, 5, 6, 7. The numbers do not have to be next to each other in the list. Print the length of that run.
Example 1
Input
7 100 4 200 1 3 2 101
Output
4
1, 2, 3, 4 form a run of 4. 100, 101 form a run of 2.
Example 2
Input
4 5 5 5 5
Output
1
Repeated numbers count once, so the run is just 5.
Try the problem first. Open one hint at a time.
Sorting works in O(n log n). Can you do it in one pass with a set?
Put every number in a HashSet, which also removes repeats.
Only start counting from a number x when x − 1 is not in the set. Then x is the start of a run.
From a start, keep checking x + 1, x + 2, ... Each number is then visited by at most one run.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor