Annettuna on bittijono, jossa jokainen merkki on $0$ tai $1$. Tehtäväsi on laskea summa kaikista bittiparien etäisyyksistä, joissa kumpikin bitti on $1$.

Esimerkiksi kun bittijono on $10110$, etäisyydet ovat seuraavat:

• $\underline{1}0\underline{1}10$ (etäisyys $2$)
• $\underline{1}01\underline{1}0$ (etäisyys $3$)
• $10\underline{1}\underline{1}0$ (etäisyys $1$)

Etäisyyksien summa on siis $2+3+1=6$.

Voit olettaa, että bittijonon pituus on enintään $10^5$. Tavoitteena on, että algoritmin aikavaativuus on $O(n)$.

Python

Toteuta tiedostoon bitpairs.py funktio calculate, joka ilmoittaa etäisyyksien summan.

def calculate(s):
    # TODO

if __name__ == "__main__":
    print(calculate("10110")) # 6
    print(calculate("10")) # 0
    print(calculate("10010110")) # 20
    print(calculate("0011110111101010")) # 214

Java

Toteuta tiedostoon BitPairs.java metodi calculate, joka ilmoittaa etäisyyksien summan.

public class BitPairs {
    public long calculate(String s) {
        // TODO
    }

    public static void main(String[] args) {
        BitPairs b = new BitPairs();
        System.out.println(b.calculate("10110")); // 6
        System.out.println(b.calculate("10")); // 0
        System.out.println(b.calculate("10010110")); // 20
        System.out.println(b.calculate("0011110111101010")); // 214
    }
}