Kth Smallest Element of a Matrix of given dimensions filled with product of indices | C ++ program for the above approach ; Function that returns true if the count of elements is less than mid ; To store count of elements less than mid ; Loop through each row ; Count elements less than mid in the ith row ; Function that returns the Kth smallest element in the NxM Matrix after sorting in an array ; Initialize low and high ; Perform binary search ; Find the mid ; Check if the count of elements is less than mid ; Return Kth smallest element of the matrix ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define LL  long long NEW_LINE bool countLessThanMid ( LL mid , LL N , LL M , LL K ) { LL count = 0 ; for ( int i = 1 ; i <= min ( ( LL ) N , mid ) ; ++ i ) { count = count + min ( mid / i , M ) ; } if ( count >= K ) return false ; else return true ; } LL findKthElement ( LL N , LL M , LL K ) { LL low = 1 , high = N * M ; while ( low <= high ) { LL mid = low + ( high - low ) / 2 ; if ( countLessThanMid ( mid , N , M , K ) ) low = mid + 1 ; else high = mid - 1 ; } return high + 1 ; } int main ( ) { LL N = 2 , M = 3 ; LL int K = 5 ; cout << findKthElement ( N , M , K ) << endl ; return 0 ; }