Challenge: k-th Smallest

Lab Python Intermediate 20 points

Read a list and a number k, and print the k-th smallest number (k = 1 is the smallest). Use the quick sort partition idea (quickselect): after partitioning, only keep searching the side that contains position k − 1.

Input

Line 1: whole numbers. Line 2: k.

Output

The k-th smallest number.

Example

Input

7 10 4 3 20 15
3

Output

Sample input available Sample output available

Editor

Python

Hints

Partition like quick sort; the pivot lands at index p.

If p == k - 1 you're done. Otherwise continue on just one side.

Solution explanation

Because only one side is kept each time, quickselect takes O(n) on average – faster than sorting everything.

Show solution

def partition(a, lo, hi):
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    return i

a = list(map(int, input().split()))
k = int(input()) - 1
lo, hi = 0, len(a) - 1
while True:
    p = partition(a, lo, hi)
    if p == k:
        print(a[p])
        break
    if p < k:
        lo = p + 1
    else:
        hi = p - 1

Output

Answer