Voit olettaa, että listalla on korkeintaan $10^5$ lukua ja $k$ on korkeintaan $10^9$. Tavoitteena on, että algoritmin aikavaativuus on $O(n)$ tai $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)) # 191628970Selitys: Jokainen kokonaisluku väliltä $1\dots 11$ on korkeintaan $3$:n päässä jostain listan $[1, 2, 9]$ luvusta. Yksi tällainen luku on esimerkiksi $5$, joka on kolmen päässä sitä lähimmästä luvusta $2$. Luku $6$ puolestaan on kolmen päässä luvusta $9$. Jokainen luku väliltä $1\dots 3$ löytyy jo valmiiksi listalta $[2, 1, 3]$. Siksi suurin etäisyys on $0$.