Maksimikekoon lisätään järjestyksessä luvut $1,2,\dots,n$. Kuinka monta kertaa kahden eri alkion paikkaa vaihdetaan keskenään keossa kyseisen prosessin aikana? Voit olettaa, että $n$ on korkeintaan $10^9$.

Esimerkiksi kun $n=4$, vaihdot ovat järjestyksessä $1 \leftrightarrow 2$, $2 \leftrightarrow 3$, $1 \leftrightarrow 4$ ja $3 \leftrightarrow 4$, joten vastaus on $4$.

Python

Toteuta tiedostoon maxheap.py fuktio count, joka antaa vaihtojen määrän.

def count(n):
    # TODO

if __name__ == "__main__":
    print(count(4)) # 4
    print(count(7)) # 10
    print(count(123)) # 618
    print(count(999999999)) # 27926258178

Java

Toteuta tiedostoon MaxHeap.java metodi count, joka antaa vaihtojen määrän.

public class MaxHeap {
    public long count(int n) {
        // TODO
    }

    public static void main(String[] args) {
        MaxHeap m = new MaxHeap();
        System.out.println(m.count(4)); // 4
        System.out.println(m.count(7)); // 10
        System.out.println(m.count(123)); // 618
        System.out.println(m.count(999999999)); // 27926258178
    }
}