Find Kth number from sorted array formed by multiplying any two numbers in the array | C # implementation to find the Kth number in the list formed from product of any two numbers in the array and sorting them ; Function to find number of pairs ; Negative and Negative ; Add Possible Pairs ; Positive and Positive ; Add Possible pairs ; Negative and Positive ; Add Possible pairs ; Function to find the kth element in the list ; Separate Positive and Negative elements ; Sort the Elements ; Binary search ; Return the required answer ; Driver code ; Function call
using System ; using System . Collections . Generic ; class GFG { static bool check ( int x , List < int > pos , List < int > neg , int k ) { int pairs = 0 ; int p = neg . Count - 1 ; int nn = neg . Count - 1 ; int pp = pos . Count - 1 ; for ( int i = 0 ; i < neg . Count ; i ++ ) { while ( ( p >= 0 ) && ( ( int ) neg [ i ] * ( int ) neg [ p ] <= x ) ) p -- ; pairs += Math . Min ( nn - p , nn - i ) ; } p = 0 ; for ( int i = pos . Count - 1 ; i >= 0 ; i -- ) { while ( ( p < pos . Count ) && ( ( int ) pos [ i ] * ( int ) pos [ p ] <= x ) ) p ++ ; pairs += Math . Min ( p , i ) ; } p = pos . Count - 1 ; for ( int i = neg . Count - 1 ; i >= 0 ; i -- ) { while ( ( p >= 0 ) && ( ( int ) neg [ i ] * ( int ) pos [ p ] <= x ) ) p -- ; pairs += pp - p ; } return ( pairs >= k ) ; } static int kth_element ( int [ ] a , int n , int k ) { List < int > pos = new List < int > ( ) ; List < int > neg = new List < int > ( ) ; ; for ( int i = 0 ; i < n ; i ++ ) { if ( a [ i ] >= 0 ) pos . Add ( a [ i ] ) ; else neg . Add ( a [ i ] ) ; } sort ( pos . begin ( ) , pos . end ( ) ) ; sort ( neg . begin ( ) , neg . end ( ) ) ; pos . Sort ( ) ; neg . Sort ( ) ; int l = ( int ) - 1e8 , ans = 0 , r = ( int ) 1e8 ; while ( l <= r ) { int mid = ( l + r ) >> 1 ; if ( check ( mid , pos , neg , k ) ) { ans = mid ; r = mid - 1 ; } else l = mid + 1 ; } return ans ; } public static void Main ( String [ ] args ) { int [ ] a = { - 4 , - 2 , 3 , 3 } ; int k = 3 ; int n = a . Length ; Console . WriteLine ( kth_element ( a , n , k ) ) ; } }