Minimum K product

Easy

0/40

Average time to solve is 20m

23 upvotes

Asked in companies

Problem statement

You are given an array 'ARR' of 'N' positive integers and a positive integer 'K'.

Your task is to find the minimum product of K integers of the given array.

Note:

You need to return the product modulo 10^9 + 7.

For Example :

If the given array is [1, 4, 2 ,6, 3] and K = 3. 
Then answer will be 6 by taking the product of integers 1, 2, and 3.

Follow Up:

Can you solve it in less than O(N * logN) time complexity?

Detailed explanation ( Input/output format, Notes, Images )

Input format :

The first line of input contains a single integer T, representing the number of test cases or queries to be run. 
Then the T test cases follow.

The first line of each test case contains two positive integers 'N' and 'K', where N is the size of the given array 'ARR' and K is the number of elements of the array of which minimum product is to be found.

The next line contains 'N' single space-separated positive integers representing the elements of the array.

Output Format :

For each test case, print an integer denoting the minimum product of K integers modulo 10^9+7 in a single line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraint :

1 <= T <= 10
1 <= N <= 10^5
1 <= ARR[i] <= 10^9
1 <= K <= N

Time Limit: 1 sec

Sample Input 1 :

1
5 3
5 2 3 8 3

Sample Output 1:

Explanation for Input 1:

The minimum product of 3 integers is obtained by choosing (2, 3, 3) which is 18.

Sample Input 2 :

1
6 3
1 2 7 2 3 2

Sample Output 2 :

Hint 1

Hint 2

Think of sorting the array.

Approaches (2)

Approach 1

Approach 2

Sorting

Sort the given array ‘ARR’ in increasing order.
Initialise a variable ‘ANS’ to 1.
Run a loop from 0 to ‘K’ and store the product of elements in the ‘ANS’ variable by taking the modulo at each multiplication.
Return the ‘ANS’ % ‘MODULO’.

Time Complexity

O(N * logN), where N is the length of the array.

We will be sorting the array that takes O(N * logN) time and for calculating product O(K) time is required. Total time complexity will be O(N * logN) + O(K) = O(N * logN).

Space Complexity

O(1).

Constant space is required.

(100% EXP penalty)

Minimum K product

Console