Problem Link I have come up with a nice idea . I will just use three vectors to keep the negative numbers(v1),zeros(v2),positive numbers(v3).
Let the size of the vectors v1,v2,v3.
Then there will be (v1* v3) negative products , ((v1*v2 + (v3*v2)) zeros , ( (v1*(v1-1))/2 + (v3*(v3-1))/2) positive products.
So I can easily know whether Kth number will be negative or zero or positive.
But I am failing to print the answer when It is a positive number. I don't know how to find the positive product which is in this -- >( (v1*(v1-1))/2 + (v3*(v3-1))/2) count.
Please Help.
First you need to split the input into two arrays one for positive numbers and the other for negative numbers, zeros can go with one of them it does not matter.
sort the arrays
Now you will binary search for the answer (The value we are looking to output as the final answer) now this value ranges between -1e18 and 1e18.
Let this number be our mid, Now we need to see how many products of two numbers are below or equal to this mid.
To do so, there is two cases:
A. We can have a pair of both numbers are positive. (so we linear scan the positive numbers array, and for each number we binary search for positive numbers in indices more than the current index, to find out how many numbers less than or equal to our mid.
B. We can have a pair of both numbers are negative (since negative multiply negative would be equal positive number) again we do linear scan over negative numbers, and then for each number we binary search for how many negative numbers when multiplied will results in a number less than or equal to our mid.
C. All positive numbers * negative numbers will results for sure in a number less than or equal to mid (since mid is positive)
Now we have our total number of pairs less than or equal to the mid.
If this number is equal k, then mid is our answer.
if this number is less than k, then our mid is too small and we need to increase so we do L = mid + 1
if this number is more than k, then our mid is too large and we need to decrease it so we do R = mid — 1;