Listalla on n kokonaislukua väliltä 1\dots k. Listalle halutaan lisätä uusi kokonaisluku väliltä 1\dots k, jonka etäisyys lähimpään listalla valmiiksi olevaan lukuun on mahdollisimman suuri. Mikä on tämä etäisyys?
Algoritmin aikavaativuuden tulee olla O(n \log n).
Toteuta tiedostoon distance.py funktio find, joka ilmoittaa suurimman mahdollisen etäisyyden.
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
Selitys: Ensimmäisessä tapauksessa vastaus on 3, koska listalle voidaan lisätä luku 5 tai 6, jolloin etäisyys on 3 (lukuun 2 tai 9). Ei ole mahdollista lisätä lukua niin, että etäisyys olisi 4 tai enemmän.