Find the Kth smallest element in the sorted generated array | C ++ implementation of the approach ; Function to return the Kth element in B [ ] ; Initialize the count Array ; Reduce N repeatedly to half its value ; Add count to start ; Subtract same count after end index ; Store each element of Array [ ] with their count ; Sort the elements wrt value ; If Kth element is in range of element [ i ] return element [ i ] ; If K is out of bound ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int solve ( int Array [ ] , int N , int K ) { int count_Arr [ N + 1 ] = { 0 } ; int factor = 1 ; int size = N ; while ( size ) { int start = 1 ; int end = size ; count_Arr [ 1 ] += factor * N ; count_Arr [ end + 1 ] -= factor * N ; factor ++ ; size /= 2 ; } for ( int i = 2 ; i <= N ; i ++ ) count_Arr [ i ] += count_Arr [ i - 1 ] ; vector < pair < int , int > > element ; for ( int i = 0 ; i < N ; i ++ ) { element . push_back ( { Array [ i ] , count_Arr [ i + 1 ] } ) ; } sort ( element . begin ( ) , element . end ( ) ) ; int start = 1 ; for ( int i = 0 ; i < N ; i ++ ) { int end = start + element [ i ] . second - 1 ; if ( K >= start && K <= end ) { return element [ i ] . first ; } start += element [ i ] . second ; } return -1 ; } int main ( ) { int arr [ ] = { 2 , 4 , 5 , 1 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int K = 13 ; cout << solve ( arr , N , K ) ; return 0 ; }