KSMALL  Kth smallest number
Given an array of (pseudo) random numbers generated by the C++ function below, your task is to find the Kth smallest number of all the numbers.
unsigned array[5000000]; void randomize(unsigned a,unsigned b,unsigned mod) { for( int i=0 ; i<5000000 ; i++ ) { a = 31014 * (a & 65535) + (a >> 16); b = 17508 * (b & 65535) + (b >> 16); array[i] = ((a << 16) + b) % mod; } }
Note that the computation might overflow, but we only care about the last 32 bit of each result so it doesn't matter.
Input
One line with 4 numbers (a, b, mod, K) separated by space.
0 < a, b < 65535
2 < mod < 2^{32}1
1 < K < 5x10^{6}
Output
Kth smallest number of all the generated numbers.
Example
Input: 2 3 100000007 23 Output: 434
hide comments
priyanshul:
20181121 13:07:06
its showing segmentation fault, what should I do? (i am using quicksort to sort the array and then reading the (k1)th element of the array. 

jmr99:
20181013 17:18:18
if(heard about ""nth_element"" stl in c++)


akki:
20170414 13:36:15
Hint: Learn 3way partitioning (quicksort). 

aakash_s:
20160923 08:29:41
I have tried O(n) approach with optimizations


sivakumarar:
20160922 19:07:43
How to find which of the 20 test case failed. Is there are way to get the test input files to test and debug it locally , before uploading the solution. 

Sarot Busala:
20150701 09:33:25
I have tried 3 different ways, one of this is O(N) approach and got only TLE. :(


:D:
20150310 22:10:15
Re Jason S: It's the sorted(array)[k1] version. That way for every K in the specified input range there is always a valid solution. 

Rahul Lingala:
20150123 21:58:07
Time limit is too strict. I know the perfect algorithm, but still my solution is not getting accepted even after optimising it to the maximum extent.


Jason S:
20140824 04:42:56
Is it supposed to be sorted(array)[k1] or the kth unique value? I have some thousands of testcases based on the former (which the example implies) that pass but am getting WA. 

anurag garg:
20140325 13:41:50
@author can you have a look at my submission:11324082

Added by:  Andy 
Date:  20140310 
Time limit:  0.100s0.246s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 