Distance of Bit pairs

userhYlH 0
Viewed 40

I am given a string, and I have to calculate the sum of of each distance of bit pairs where both bits are 1.

For example the given string of 100101 would have the distance of 10
100101 (3)
100101 (5)
100101 (2)

Therefore the sum of distances is 3+5+2=10.

My current code is the following, I can't really solve what's wrong, and how should I approach the problem.

def pairs(s):
    count = 0
    for i in range(len(s)):
        if s[i] == '1':
            for j in range(i+1, len(s)):
                if s[j] == '1':
                    count += 1
    return count

if __name__ == "__main__":
    print(pairs("100101")) #10

I have also tried to store the 1's in a list, but can't manage to calculate the distance.

data-structures sorting python-3.x algorithm
2 Answers

The following should do it:

def pairs(s):
    count = 0
    for i in range(len(s)):
        if s[i] == '1':
            dist = 0
            for j in range(i+1, len(s)):
                dist += 1
                if s[j] == '1':
                    count += dist
    return count

if __name__ == "__main__":
    print(pairs("100101")) #10
Axel Kemper0

Try itertools.combinations on indices where the char == 1:

from itertools import combinations

s = "100101"

indices = [i for i, ch in enumerate(s) if ch == "1"]
print(sum(b - a for a, b in combinations(indices, 2)))

Prints:

10
Andrej Kesely0
Related