Bitset Rank Query

Problem

Compute rank queries on a bitset.

rank(i) is the number of 1-bits at positions 0 through i inclusive. bits is the bit list and queries holds the positions; an index past the end counts the whole array and an empty bitset returns 0.

Return the rank for each query.

Hint

Rank is the prefix sum up to the requested position, clamped to the last index.

Test cases

case 1

in: [[1,0,1,1,0],[0,1,2,3,4]]

expected: [1,1,2,3,3]

case 2

in: [[0,0],[0,1]]

expected: [0,0]

case 3

in: [[],[0]]

expected: [0]

case 4

in: [[1,1,1],[2]]

expected: [3]

Starter codePython

def bitset_rank(bits, queries):
    # Your code here
    pass

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