def kth_number(lst: list[int], k: int) -> int:
    # pick a pivot and separate into list based on pivot.
    pivot = random_pivot(lst)

    # partition based on pivot
    # linear time
    small = [e for e in lst if e < pivot]
    big = [e for e in lst if e > pivot]

    # if we get lucky, pivot might be the element we want.
    # we can easily see this:
    # small (elements smaller than k)
    # + pivot (kth element)
    # + big (elements larger than k)
    if len(small) == k - 1:
        return pivot
    # pivot is in elements bigger than k
    elif len(small) < k - 1:
        return kth_number(big, k - len(small) - 1)
    # pivot is in elements smaller than k
    else:
        return kth_number(small, k)