Small sums

Consider the set \{1,2,\dots,10^9\}. Your task is to compute the nth smallest sum of a subset.

The time complexity of the algorithm should be O(n \log n).

In a file smallsum.py, implement a function find that returns the desired answer.

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