Your task is to implement a class that maintains a list of numbers and has a method that reports how many distinct occurrence counts the numbers on the list have. The occurrence count of a number tells how many times that number occurs on the list.
For example, the list has just one occurrence count because each number occurs twice on the list. The list has three occurrence counts, because the number occurs once, the number occurs twice and the number occurs three times.
In a file occurrences.py
, implement the class OccurrenceTracker
with the following methods:
append(number)
: addnumber
to the end of the listcount()
: return the number of distinct occurrence counts
Both methods should work in time.
class OccurrenceTracker: def __init__(self): # TODO def append(self, number): # TODO def count(self): # TODO if __name__ == "__main__": tracker = OccurrenceTracker() tracker.append(1) tracker.append(2) tracker.append(1) tracker.append(3) print(tracker.count()) # 2 tracker.append(2) tracker.append(3) print(tracker.count()) # 1 tracker.append(2) tracker.append(3) tracker.append(3) print(tracker.count()) # 3
You can test the efficiency of your solution with the following code. In this case too the code should finish almost immediately.
tracker = OccurrenceTracker() total = 0 for i in range(10**5): tracker.append(i % 100 + 1) total += tracker.count() print(total) # 198901