text: Kth smallest element in an array that contains A [ i ] exactly B [ i ] times | C ++ program for the above approach ; Function to find the Kth smallest element that contains A [ i ] exactly B [ i ] times ; Traverse the given array ; Stores the frequency of every elements ; Traverse the given array ; Initialize a variable to store the prefix sums ; Iterate over the range [ 0 , M ] ; Increment sum by freq [ i ] ; If sum is greater than or equal to K ; Return the current element as answer ; Return - 1 ; Driver Code ; Given Input ; Function call
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; int KthSmallest ( int A [ ] , int B [ ] , int N , int K ) { int M = 0 ; for ( int i = 0 ; i < N ; i ++ ) { M = max ( A [ i ] , M ) ; } int freq [ M + 1 ] = { 0 } ; for ( int i = 0 ; i < N ; i ++ ) { freq [ A [ i ] ] += B [ i ] ; } int sum = 0 ; for ( int i = 0 ; i <= M ; i ++ ) { sum += freq [ i ] ; if ( sum >= K ) { return i ; } } return -1 ; } int main ( ) { int A [ ] = { 3 , 4 , 5 } ; int B [ ] = { 2 , 1 , 3 } ; int N = sizeof ( A ) / sizeof ( A [ 0 ] ) ; int K = 4 ; cout << KthSmallest ( A , B , N , K ) ; return 0 ; }