Tarkastellaan joukkoa \{1,2,\dots,10^9\}. Tehtäväsi on laskea, mikä on joukon n:nneksi pienimmän osajoukon summa.
Algoritmin aikavaativuuden tulee olla O(n \log n).
Toteuta tiedostoon smallsum.py funktio find, joka palauttaa tehtävän vastauksen.
def find(n):
# TODO
if __name__ == "__main__":
print(find(1)) # 0
print(find(2)) # 1
print(find(3)) # 2
print(find(4)) # 3
print(find(5)) # 3
print(find(123)) # 15
print(find(123456)) # 62