The length of each array A,B and C <= 1000 and K <= min(10^6, na * nb * nc) (na,nb,nc is the length of each array A,B and C)
I have thought that we can run through array A and B to find all the products of A and B in O(n^2) and generate Kth number by multiply that products with element in array C. But I don't know how to exactly generate Kth number in step 2th.
In this problem, the number can be NEGATIVE
Does anyone help me about this or give me your idea how to solve this problem? Thank you!
Think about binary search for the answer.
Good day to you,
imho "some" approach could be:
Binary search by Answer: so now you know the answer and question transforms to "Is there exactly K elements (a*b*c) lesser then "something"?"
For arrays A,B make full O(N^2) iteration, so you always have some "a*b" and you know perfectly well which range of numbers makes it lesser/equal to "something" (the answer you found by binary search) [maybe some if for negatives? — but shall be similar]
Binary-search in sorted array C, to find your "range" — i.e. find the number of elements which will make "a*b*c" lesser.
So guess this is it — I hope I understood your problem well.
Complexity shall be O(Nlog(N)*log(MAX(A[i]*B[i]))) — hope it is enough.
Also hope it is a little bit understandable.
Have nice day,
Good Luck
PS: Don't hesitate to pose questions ^_^
~/Morass
Thank you so much! Now I understand it :D
Sr, I have a little trouble here! Assume our array A * B * C is :
-12 -8 -6 -4 0 0 0 1 2 The 4th number is -4, but in my binary search, the median which is number -3 also has 3 numbers(-12 -8 -6) which is less than -3. But the problem is -3 is not in an array and I don't know whether my left and right in binary search should be mid -1 or mid + 1. How can we deal with this situation ?
sort all three arrays. Now make a priority_queue and do, the following.
Insert in the priority_queue a[n - 1] × b[n - 1] × c[n - 1] and a[0] × b[0] × c[0]. Now, take the topmost element of queue. Let's say the maximum tuple is (i, j, k), then insert in your priority queue the following tuples (i, j, k - 1), (i, j - 1, k), (i - 1, j, k), (i + 1, j, k), (i, j + 1, k), (i, j, k + 1). Keep tracks of the tuples visited in a map so you don't use some tuples more than once. and keep on doing this until you've encountered Kth maximum number.
After generate the A*B, binary search x in [0, 106] to find how many A*B*C number isn't greater x.
Can you give the problem link?
There was a problem from Google Kick-start 2017 round D , in which you had to compute the kth smallest pairwise product between 2 arrays . You can check out the editorial .
Problem Link