Find Kth number from sorted array formed by multiplying any two numbers in the array | 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
function check ( x , pos , neg , k ) { let pairs = 0 ; let p = neg . length - 1 ; let nn = neg . length - 1 ; let pp = pos . length - 1 ; for ( let i = 0 ; i < neg . length ; i ++ ) { while ( ( p >= 0 ) && ( neg [ i ] * neg [ p ] <= x ) ) p -- ; pairs += Math . min ( nn - p , nn - i ) ; } p = 0 ; for ( let i = pos . length - 1 ; i >= 0 ; i -- ) { while ( ( p < pos . length ) && ( pos [ i ] * pos [ p ] <= x ) ) p ++ ; pairs += Math . min ( p , i ) ; } p = pos . length - 1 ; for ( let i = neg . length - 1 ; i >= 0 ; i -- ) { while ( ( p >= 0 ) && ( neg [ i ] * pos [ p ] <= x ) ) p -- ; pairs += pp - p ; } return ( pairs >= k ) ; } function kth_element ( a , n , k ) { let pos = [ ] ; let neg = [ ] ; for ( let i = 0 ; i < n ; i ++ ) { if ( a [ i ] >= 0 ) pos . push ( a [ i ] ) ; else neg . push ( a [ i ] ) ; } sort ( pos . begin ( ) , pos . end ( ) ) ; sort ( neg . begin ( ) , neg . end ( ) ) ; pos . sort ( function ( a , b ) { return a - b } ) ; neg . sort ( function ( a , b ) { return a - b } ) ; let l = - 1e8 , ans = 0 , r = 1e8 ; while ( l <= r ) { let mid = ( l + r ) >> 1 ; if ( check ( mid , pos , neg , k ) ) { ans = mid ; r = mid - 1 ; } else l = mid + 1 ; } return ans ; } let a = [ - 4 , - 2 , 3 , 3 ] ; let k = 3 ; let n = a . length ; document . write ( kth_element ( a , n , k ) ) ;