Saat syötteenä listan, joka sisältää n kokonaislukua.
Tarkastellaan prosessia, jossa valitset joka askeleella listan kaksi pienintä lukua, poistat ne listasta ja lisäät listan loppuun näiden lukujen summan vähennettynä yhdellä. Jatkat näin, kunnes listalla on vain yksi luku. Mikä tämä luku on?
Tehtäväsi on laatia tehokas algoritmi, joka selvittää annetun listan viimeisen luvun. Algoritmin aikavaativuuden tulee olla O(n).
Toteuta tiedostoon lastnumber.py funktio find, joka palauttaa listan viimeisen luvun.
def find(t):
# TODO
if __name__ == "__main__":
print(find([1,2,3,4])) # 7
print(find([1,1,1])) # 1
print(find([5,1,1,7,9,1,2])) # 20
Selitys: Kun lista on [1,2,3,4], poistat aluksi luvut 1 ja 2 ja lisäät luvun 2. Tämän jälkeen lista on [3,4,2]. Sitten poistat luvut 3 ja 2 ja lisäät luvun 4, jolloin lista on [4,4]. Lopuksi poistat luvut 4 ja 4 ja lisäät luvun 7, jolloin lista on [7].