# K-th smallest element in unsorted array

Given an array v of distinct numbers, and a number k where k is smaller than the size of v, find the k-th smallest element in the array. A simple solution would be first sorting the array in growing order and than selecting the k-th element which can be done in θ(n logn). However, your program MUST run in θ(n) on average.

Difficulty: Medium.

### Input

There are two lines.

• The first line contains an integer `k`
• The second line contains an integer `l` such that `k`<=`l` and `l` is the length of the array v.
• The second line consists of `l` numbers separated by space which represent the array v.

At the end of each line, there are no extra spaces, and there is a `\n`.

### Output

One line containing 1 integer, which is the k-th smallest number in v.

### Example

Input:

`3`

`5`

`3 5 2 8 4`

Output:

`4`

### Hint

You can borrow the idea of Quicksort.

### Solution: C++

```#include<stdlib.h>
#include<stdio.h>
#include<iostream>

using namespace std;

void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}

int partition(int v[], int l, int r){
// same as quicksort
int p = v[r-1]; // pivot is the last element
int j=l;
for(int i=l;i<r-1;i++){
if(v[i]<p){
swap(&v[i], &v[j]);
j++;
}
}
swap(&v[j], &v[r-1]);
return j;
}

void find_k_smallest(int v[], int k, int l, int r){
//find the pivot such that v[0...p-1]<v[p]<v[p+1...l]
int p = partition(v, l, r);
//if the pivot is the k-th element, we are done since v[0...k-1]<v[k]<v[k+1...l]
if(p==k-1){
cout<<v[p];
return;
}
//the solution is in v[0...p-1]
if(p>k-1)
find_k_smallest(v, k, l, p);
//the solution is in v[p+1...l]
find_k_smallest(v, k, p+1, r);
}

int main(){
int k;
cin>>k; //index k of the k-th smallest number in the array
int l;
cin>>l; //length of the array
int v[l];
for(int i=0; i<l; i++)
cin>>v[i];
find_k_smallest(v, k, 0, l);
}

```