Pienet summat

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