Find K-Th Element From Product Array.

Hard
0/120
Average time to solve is 45m
profile
Contributed by
25 upvotes
Asked in companies
SAP LabsMicrosoft

Problem statement

You are given an integer array ‘Arr’ of length ‘N’. Your task is to find the Kth element of the ‘product’ array when the ‘product’ array is sorted in non-decreasing order.

The ‘product’ array of ‘Arr’ is an array of size (N*(N-1)) / 2 which consist multiplication of each pair of elements present in the array ‘Arr’, i.e product[k] = Arr[i] * Arr[j], where 0 ≤ i < j < ‘N’.

Note :

Return -1 if the value of ‘K’ exceeds the number of elements in the array ‘product’.

For Example :

Input array “arr”= [1, 2, 3, 4] and K = 3
Output: 4 

Explanation: The ‘product’ array i.e array formed by multiplying each pair of element of ‘Arr’ is [1*2, 1*3, 1*4, 2*3, 2*4, 3*4] = [2, 3, 4, 6, 8, 12]. So the Kth(K = 3) element in this sorted ‘product’ array is 4.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains two integers separated by a single space i.e N and K.

The second and last line of each test case contains N single space-separated integers representing the elements of the input array ‘Arr’.
Output Format : 
For each test case, print the Kth element of the ‘product’ array after sorting it in non-decreasing order.

Output for every test case will be printed in a separate line.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 50
1 <= N <= 10^4
1 <= K <= 10^9
-10^4 <= Arr[i] <= 10^4

Time Limit: 1 sec
Sample Input 1 :
2
4 2
1 2 3 -1
3 2
-1 0 1
Sample Output 1 :
-2
0
Explanation For Sample Input 1 :
Test Case 1:
The ‘product’ array formed by multiplying any two numbers taken two at a time is : [-1 * 1, -1 * 2, -1 * 3, 1 * 2, 1 * 3, 2 * 3] = [-1, -2, -3, 2, 3, 6] and this array after sorting  is: [-3, -2, -1, 2, 3, 6]. So the 2nd element in the sorted ‘product’ array is -2.

Test Case 2:
The ‘product’ array formed by multiplying any two numbers taken two at a time is : [-1 * 0, -1 * 1, -0 * 1] [0, -1] and sorted ‘product’ array is: [-1, 0, 0]. So the 2nd element in the sorted ‘product’ array is 0.
Sample Input 2 :
2
3 5
1 3 4
1 1
-1
Sample Output 2 :
-1
-1
Hint

Find product of all pairs

Approaches (3)
Brute Force
  • Check for the base case i.e. if k > N * (N - 1) / 2, simply return -1.
  • Initialize a vector named ‘product’.
  • Now we will push all possible products of pairs into the array.
  • while(i < N)
    • while(j > i and j < N)
      • product.push(arr[i] * arr[j])
  • Sort the ‘product’ and return the Kth number in the array ‘product’.
Time Complexity

O(N * N * log(N)), where N is the number of elements in the array.

 

The size of array ‘product’ will be N * (N - 1) / 2, i.e of the order of N * N. Sorting this array ‘product’ takes time O((N * N) * log(N * N))  = O(2 * (N * N) * log(N)) or O((N * N) * log(N)).

Space Complexity

O(N * N), where N is the number of elements in the array.

 

The size of array ‘product’ will be N * (N - 1) / 2, i.e of the order of

N * N.

Code Solution
(100% EXP penalty)
Find K-Th Element From Product Array.
Full screen
Console