Andrew is a stock trader who trades in N selected stocks. He has calculated the relative stock price changes in the N stocks from the previous day stock prices. Now, his lucky number is K, so he wishes to invest in the particular stock that has Kth smallest relative stock value. Write an algorithm for Andrew to find the Kth smallest stock price out of the selected N stocks.
Input
The first line of the input consists of two space-separated integers – numOfStocks and valuek, representing the number of selected stocks (N) And the value K for which he wishes to find the stock price, respectively. The second line consists of N space-separated integers – stock1, stock2, ……, stock N
representing the relative stock prices of the selected stocks.
Output
Print an integer representing the Kth smallest stock price of selected N stocks.
Constraints
0 <valueK ≤ numOfStocks ≤ 106
0 ≤ stocki ≤ 106
0 ≤ i<numOfStocks
Example
Input:
7 5
9 -3 8 -6 -7 18 10
Output:
9
Explanation:
The sorted relative stock prices are [-7, -6, -3, 8, 9, 10, 18]
So, the 5th smallest stock price is 9.
Solution: In C
#include <stdio.h>
int main()
{
int n,k;
scanf("%d %d", &n,&k);
int a[n],i,j,t;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<n-1;i++)
{
for(j=0;j<n-1-i;j++)
{
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
printf("%d",a[k-1]);
}Also Checkout