Annettuna on merkkijono, jonka jokainen merkki on 0 tai 1. Saat jokaisella siirrolla vaihtaa kaksi vierekkäistä merkkiä keskenään, ja tehtäväsi on siirtää kaikki 0-merkit ennen 1-merkkejä. Mikä on pienin määrä siirtoja?

Esimerkiksi merkkijonossa 101010 tarvitaan ainakin 6 siirtoa. Tässä on yksi optimaalinen ratkaisu:

101010 \rightarrow 101001 \rightarrow 011001 \rightarrow 010101 \rightarrow 001101 \rightarrow 001011 \rightarrow 000111

Voit olettaa, että merkkijonossa on enintään 10^5 merkkiä. Tavoitteena on, että algoritmin aikavaativuus on O(n) tai O(n \log n).

Python

Toteuta tiedostoon bitsort.py funktio solve, joka antaa pienimmän siirtojen määrän.

def solve(s):
    # TODO

if __name__ == "__main__":
    print(solve("000100")) # 2
    print(solve("111000")) # 9
    print(solve("101010")) # 6

Java

Toteuta tiedostoon BitSort.java metodi solve, joka antaa pienimmän siirtojen määrän.

public class BitSort {
    public long solve(String s) {
        // TODO
    }

    public static void main(String[] args) {
        BitSort b = new BitSort();
        System.out.println(b.solve("000100")); // 2
        System.out.println(b.solve("111000")); // 9
        System.out.println(b.solve("101010")); // 6
    }
}