Count-Distinct Lower Bound

Problem

Return a lower bound on the number of distinct values in a stream of stream_len observations.

If the most frequent value occurs max_frequency times, every distinct value accounts for at most that many observations, so there are at least ceil(stream_len / max_frequency) distinct values. Return 0 when either argument is non-positive.

Hint

The heaviest hitter caps how much of the stream a single distinct value can explain.

Test cases

case 1

in: [100,5]

expected: 20

case 2

in: [101,5]

expected: 21

case 3

in: [0,3]

expected: 0

case 4

in: [10,1]

expected: 10

case 5

in: [7,10]

expected: 1

Starter codePython

def count_distinct_lower_bound(stream_len, max_frequency):
    # Your code here
    pass

5 test cases · run your code against them in the editor