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
def check ( x , pos , neg , k ) : NEW_LINE INDENT pairs = 0 NEW_LINE p = len ( neg ) - 1 NEW_LINE nn = len ( neg ) - 1 NEW_LINE pp = len ( pos ) - 1 NEW_LINE for i in range ( len ( neg ) ) : NEW_LINE INDENT while ( p >= 0 and neg [ i ] * neg [ p ] <= x ) : NEW_LINE INDENT p -= 1 NEW_LINE DEDENT pairs += min ( nn - p , nn - i ) NEW_LINE DEDENT p = 0 NEW_LINE for i in range ( len ( pos ) - 1 , - 1 , - 1 ) : NEW_LINE INDENT while ( p < len ( pos ) and pos [ i ] * pos [ p ] <= x ) : NEW_LINE INDENT p += 1 NEW_LINE DEDENT pairs += min ( p , i ) NEW_LINE DEDENT p = len ( pos ) - 1 NEW_LINE for i in range ( len ( neg ) - 1 , - 1 , - 1 ) : NEW_LINE INDENT while ( p >= 0 and neg [ i ] * pos [ p ] <= x ) : NEW_LINE INDENT p -= 1 NEW_LINE DEDENT pairs += pp - p NEW_LINE DEDENT return ( pairs >= k ) NEW_LINE DEDENT def kth_element ( a , n , k ) : NEW_LINE INDENT pos , neg = [ ] , [ ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( a [ i ] >= 0 ) : NEW_LINE INDENT pos . append ( a [ i ] ) NEW_LINE DEDENT else : NEW_LINE INDENT neg . append ( a [ i ] ) NEW_LINE DEDENT DEDENT pos = sorted ( pos ) NEW_LINE neg = sorted ( neg ) NEW_LINE l = - 10 ** 18 NEW_LINE ans = 0 NEW_LINE r = 10 ** 18 NEW_LINE while ( l <= r ) : NEW_LINE INDENT mid = ( l + r ) >> 1 NEW_LINE if ( check ( mid , pos , neg , k ) ) : NEW_LINE INDENT ans = mid NEW_LINE r = mid - 1 NEW_LINE DEDENT else : NEW_LINE INDENT l = mid + 1 NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT a = [ - 4 , - 2 , 3 , 3 ] NEW_LINE k = 3 NEW_LINE n = len ( a ) NEW_LINE print ( kth_element ( a , n , k ) ) NEW_LINE