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
    }
}