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
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool check ( long long x , vector < int > & pos , vector < int > & neg , int k ) { long long 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 and neg [ i ] * neg [ p ] <= x ) p -- ; pairs += min ( nn - p , nn - i ) ; } p = 0 ; for ( int i = pos . size ( ) - 1 ; i >= 0 ; i -- ) { while ( p < pos . size ( ) and pos [ i ] * pos [ p ] <= x ) p ++ ; pairs += min ( p , i ) ; } p = pos . size ( ) - 1 ; for ( int i = neg . size ( ) - 1 ; i >= 0 ; i -- ) { while ( p >= 0 and neg [ i ] * pos [ p ] <= x ) p -- ; pairs += pp - p ; } return ( pairs >= k ) ; } long long kth_element ( int a [ ] , int n , int k ) { vector < int > pos , neg ; for ( int i = 0 ; i < n ; i ++ ) { if ( a [ i ] >= 0 ) pos . push_back ( a [ i ] ) ; else neg . push_back ( a [ i ] ) ; } sort ( pos . begin ( ) , pos . end ( ) ) ; sort ( neg . begin ( ) , neg . end ( ) ) ; long long l = -1e18 , ans = 0 , r = 1e18 ; while ( l <= r ) { long long mid = ( l + r ) >> 1 ; if ( check ( mid , pos , neg , k ) ) { ans = mid ; r = mid - 1 ; } else l = mid + 1 ; } return ans ; } int main ( ) { int a [ ] = { -4 , -2 , 3 , 3 } , k = 3 ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; cout << kth_element ( a , n , k ) ; return 0 ; }