Sparse vs Dense Check

Problem

Classify a graph as sparse or dense using the classic O(n log n) edge bound.

Given n nodes and m edges, compute threshold = n times floor(log2(n)) for n >= 2 and 0 otherwise. Return [threshold, m, label] where label is "sparse" when m <= threshold and "dense" otherwise.

Hint

n.bit_length() - 1 equals floor(log2(n)) for n >= 1, so no import is needed.

Test cases

case 1

in: [8,24]

expected: [24,24,"sparse"]

case 2

in: [8,25]

expected: [24,25,"dense"]

case 3

in: [1,0]

expected: [0,0,"sparse"]

case 4

in: [4,6]

expected: [8,6,"sparse"]

case 5

in: [10,40]

expected: [30,40,"dense"]

Starter codePython

def sparse_or_dense(n, m):
    # Your code here
    pass

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