How to solve this question?

general
1

Can only think of brute force :<

2

Try binary search.

3

explain your solution a bit.

4

I couldn’t solve it, although you can find some explanation here:

1 Like
5

i just saw this damn
both D and E were tough man XD

2 Likes
6

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 :slight_smile:

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]=1 . Mid-value[j]=8 , product =a[1].a[7]=8 , this is less than 77, so we increase the mid-value in binary search till we get a[1].a[j]>77
We realize all 11 pairs((a[1],a[2]),(a[1],a[3]).......) have product less than 77.
In this step, we did binary search in the range [2,12]
So, ans=ans+11

Step-2 :- Now, we are at index-'2' and a[2]=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[3]=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) :slight_smile:

7 Likes
7

Are u still solving the question for negative part??