Can only think of brute force :<
Try binary search.
explain your solution a bit.
I couldn’t solve it, although you can find some explanation here:
i just saw this damn
both D and E were tough man XD
Ok , this is double binary search .
I’ll first explain the easier version of this problem , which will help you in understanding the original problem’s solution .
Sort the input-array.
Lets define x,y,z as number of pairs with negative value , zero value , positive-value.
You can calculate these without any effort
Say , the given array is fully positive :- [1,2,4,5,6,7,8,9,11,12,13,14]
And the question is to find the number of pairs whose product is less than 77 .
We can do it in O(N.logN) using binary search .
Step-1 : We are at index-'1' and a=1 . Mid-value[j]=8 , product =a.a=8 , this is less than 77, so we increase the mid-value in binary search till we get a.a[j]>77
We realize all 11 pairs((a,a),(a,a).......) have product less than 77.
In this step, we did binary search in the range [2,12]
Step-2 :- Now, we are at index-'2' and a=2 (Now, we will binary search in the range [3,12]) . Repeat the same process we did at step-1.
Step-3 :- Now, we are at index-'3' and a=4 (Now, we will binary search in the range [4,12]) . Repeat the same process we did at step-1.
Step-4 :- And so on…till you reach index 'n' .
And ans has the count of all products with values less than 77.
Now, we can solve the harder version of this problem using double binary-search .
(Will add its explanation-soon)
Are u still solving the question for negative part??