Bitset Select Query

Problem

Find the position of the k-th set bit in a bitset.

bits is a list of 0s and 1s and queries holds 1-based ranks. Scan left to right and report the index of the k-th 1-bit.

Return -1 when the bitset has fewer than k set bits.

Hint

Select is the inverse of rank: count set bits until the k-th is found.

case 1

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

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

case 2

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

expected: [-1]

case 3

in: [[],[1]]

expected: [-1]

case 4

in: [[1,1,1],[3]]

expected: [2]

Starter codePython

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

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