Distances between same numbers in list using single for loop

Question

I have an assignment to get distances of every occurrence of same number in string and its time complexity should be O(n) so it shouldn't use nested for loops.

For example if my string contains "100101" and I need to get distances between ones it's total distance would be 10. (Since first and second has distance of 3, first and last has 5 and second and last has 2).

I do get the correct answers using nested for loops but I don't understand how this should be implemented without nested loops.

My current code:

def pairs(s):
    array = []
    total = 0

    for i in range(len(s)):
        if s[i] == "1":
            array.append(i)

    for k in reversed(array):
        array.remove(k)
        for j in reversed(array):
            total += k - j
        
    return total



if __name__ == "__main__":
    print(pairs("100101")) # 10
    print(pairs("101")) # 2
    print(pairs("100100111001")) # 71

Riccardo Bucco · Answer

This can be indeed computed in linear time (I adapted the classic greedy algorithm used to compute the sum of Manhattan distances of sorted points):

def pairs(numbers, target):
    result = s = i = 0
    for j, n in enumerate(numbers):
        if n == target:
            result += (j * i - s)
            s += j
            i += 1
    return result

Some examples:

>>> pairs('100101', '1')
10
>>> pairs('100101', '0')
6
>>> pairs('100010101', '1')
26

Kelly Bundy · Answer

Another variant:

def pairs(s):
    total = ones = distance = 0
    for digit in s:
        if digit == '1':
            ones += 1
            total += distance
        distance += ones
    return total

ones: The number of 1s seen so far.

total: The sum of distances between the 1s seen so far.

distance: the sum of distances of previous 1s to the current position.

When you come across another 1, count it (ones += 1) and add its sum of distances to all previous 1s to the overall total (total += distance).

When you move to the next position, you move one position away from all 1s seen so far, hence distance += ones.

Yves Daoust · Answer

Here is the logic: for the string 100100111001, the direct distances between the ones are 3, 3, 1, 1, 3. Then the distances with one intermediate step are obtained by addition: 6, 4, 2, 4. The distances with two intermediate steps: 7, 5, 5 ... We can form the complete triangle

The total is indeed 71. Now if we count the number of times every immediate distance is taken, we have 5.3 + 8.3 + 9.1 + 8.1 + 5.3 = 71. The coefficients 5, 8, 9, 8, 5 are always the same for a triangle of this size.

For increasing sizes, we have the following table of coefficients:

              1
            2   2
          3   4   3
        4   6   6   4
      5   8   9   8   5
    6  10  12  12  10   6
  7  12  15  16  15  12   7

It is easy to see the pattern by following the diagonal lines: this is just a table of multiplication. So horizontally in the row r, the coefficients are c.(r+1-c) for c=1, 2, ... r.

Finally, one can solve the problem by scanning the string, finding the successive distances and weighting them with the above coefficients. Anyway, as r is not known beforehand, on can sum separately c.d and c².d (where d is a distance), and when r is known combine (r+1)Σc.d and Σc²d.

E.g.

Σc.d = 1.3 + 2.3 + 3.1 + 4.1 + 5.3 = 31,
Σc².d = 1.3 + 4.3 + 9.1 + 16.1 + 25.3 = 115, and finally
6.31-115 = 71.

Distances between same numbers in list using single for loop

3 Answers