Find Kth number from sorted array formed by multiplying any two numbers in the array | Java 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
import java . util . * ; class GFG { static boolean check ( int x , Vector pos , Vector neg , int k ) { int pairs = 0 ; int p = neg . size ( ) - 1 ; int nn = neg . size ( ) - 1 ; int pp = pos . size ( ) - 1 ; for ( int i = 0 ; i < neg . size ( ) ; i ++ ) { while ( ( p >= 0 ) && ( ( int ) neg . get ( i ) * ( int ) neg . get ( p ) <= x ) ) p -- ; pairs += Math . min ( nn - p , nn - i ) ; } p = 0 ; for ( int i = pos . size ( ) - 1 ; i >= 0 ; i -- ) { while ( ( p < pos . size ( ) ) && ( ( int ) pos . get ( i ) * ( int ) pos . get ( p ) <= x ) ) p ++ ; pairs += Math . min ( p , i ) ; } p = pos . size ( ) - 1 ; for ( int i = neg . size ( ) - 1 ; i >= 0 ; i -- ) { while ( ( p >= 0 ) && ( ( int ) neg . get ( i ) * ( int ) pos . get ( p ) <= x ) ) p -- ; pairs += pp - p ; } return ( pairs >= k ) ; } static int kth_element ( int a [ ] , int n , int k ) { Vector pos = new Vector ( ) ; Vector neg = new Vector ( ) ; ; 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 ( ) ) ; Collections . sort ( pos ) ; Collections . sort ( neg ) ; 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 } , k = 3 ; int n = a . length ; System . out . println ( kth_element ( a , n , k ) ) ; } }