Sparse Table Build Size

Problem

A sparse table over an array of length n has one level per power of two up to n, and level j holds aggregates for intervals of length 2^j, so it stores n - 2^j + 1 entries for 2^j <= n. Return [levels, total_entries] for n >= 0.

Hint

Sum n - 2^j + 1 over every power of two 2^j that is at most n.

Test cases

case 1

in: [0]

expected: [0,0]

case 2

in: [1]

expected: [1,1]

case 3

in: [5]

expected: [3,11]

case 4

in: [8]

expected: [4,21]

Starter codePython

def sparse_table_size(n):
    # Your code here
    pass

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