Your task is to implement a class that maintains a list of numbers and has a method for efficiently computing the sum of distances between all pairs of occurrences of a given number.
For example, when the list is , the distances for the number are:
- positions and : distance
- positions and : distance
- positions and : distance
- positions and : distance
- positions and : distance
- positions and : distance
Thus the sum of the distances is .
In a file distances.py
, implement the class DistanceTracker
with the methods:
append(number)
: addnumber
to the end of the listsum(number)
: return the sum of distances fornumber
Both methods should work in time.
class DistanceTracker: def __init__(self): # TODO def append(self, number): # TODO def sum(self, number): # TODO if __name__ == "__main__": tracker = DistanceTracker() tracker.append(1) tracker.append(2) tracker.append(1) tracker.append(3) tracker.append(3) tracker.append(1) tracker.append(2) tracker.append(1) print(tracker.sum(1)) # 24 print(tracker.sum(2)) # 5 print(tracker.sum(3)) # 1 tracker.append(1) tracker.append(2) tracker.append(3) print(tracker.sum(1)) # 42 print(tracker.sum(2)) # 16 print(tracker.sum(3)) # 14
If a number does not appear on the list or appears only once, the desired result is :
tracker = DistanceTracker() print(tracker.sum(1)) # 0 tracker.append(1) print(tracker.sum(1)) # 0
You can test the efficiency of your solution with the following code. In this case too the code should finish almost immediately.
tracker = DistanceTracker() total = 0 for i in range(10**5): tracker.append(1) total += tracker.sum(1) print(total) # 4166749999583325000