Loading...
Loading...
Loading...
A coaching centre has the scores of n students in an aptitude test. If the scores were written from lowest to highest, the centre wants the biggest jump between two neighbouring scores. A big jump shows where the class splits into groups.
Print that biggest jump. If there is only one score, print 0. Try to do it in O(n) time, without a full sort.
Example
Input
6 42 7 91 15 60 33
Output
31
Sorted: 7 15 33 42 60 91. The jumps are 8, 18, 9, 18 and 31, so the answer is 31.
Try the problem first. Open one hint at a time.
Between the lowest score min and the highest score max there are n - 1 jumps. Their average is (max - min) / (n - 1), so the biggest jump is at least that.
Split the range into buckets narrower than that. Two scores in the same bucket are closer than the biggest jump, so the answer never sits inside a bucket.
Keep only the smallest and largest score of each bucket. The answer is the biggest difference between a bucket's smallest score and the largest score of the nearest non-empty bucket before it.
Handle n = 1 and all equal scores first, and use long for the range calculations.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor