starkkk's blog

How to find Kth smallest number in an array which formed by product of each element of 3 array A,B,C? (Time limit :2s)
By starkkk, history, 7 years ago, In English

Here is the full description of the problem

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!

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Think about binary search for the answer.

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Good day to you,

imho "some" approach could be:

  1. 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"?"

  2. 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]

  3. 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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Thank you so much! Now I understand it :D

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 ?

    → Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

After generate the A*B, binary search x in [0, 106] to find how many A*B*C number isn't greater x.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you give the problem link?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply