A list contains integers in the range . We want to add another integer in the range to the list so that the distance of the new number to the nearest old number is as large as possible. What is this distance?
The time complexity of the algorithm should be .
In a file distance.py
, implement a function find
that returns the maximal distance.
def find(t, k): # TODO if __name__ == "__main__": print(find([1, 2, 9], 11)) # 3 print(find([2, 1, 3], 3)) # 0 print(find([7, 4, 10, 4], 10)) # 3 print(find([15, 2, 6, 4, 18], 20)) # 4 print(find([41222388, 392676742, 307110407, 775934683, 25076911], 809136843)) # 191628970
Explanation: In the first case, the result is , because we can add the number or so that the distance (to or ) is . It is not possible to add a number so that the distance is or more.