# Minimum K product

Posted: 23 Sep, 2020

Difficulty: Easy

#### 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?
```

##### 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
```

Approach 1

Approach 2

- Initialize a variable ‘ANS’ to 1 to store the product.
- Build a Max-Heap of the first ‘K’ elements of the given array.
- For each element from ‘K’ to ‘N’, compare it with the root element of the Max-Heap.
- If the element is greater than the root element then ignore it.
- Else pop the root element and add the current element into the heap.

- Multiply all the elements that are currently in the Max-Heap by taking the modulo at each multiplication, and update the variable ‘ANS’.
- Return the ‘ANS’ % ‘MODULO’.

SIMILAR PROBLEMS

# Game of 3

Posted: 11 Jul, 2021

Difficulty: Easy

# Lexicographic Permutation Rank

Posted: 13 Jul, 2021

Difficulty: Moderate

# Zero Pair Sum

Posted: 22 Jul, 2021

Difficulty: Moderate

# Implement a Queue

Posted: 27 Jul, 2021

Difficulty: Easy

# Remove K Corner Elements

Posted: 31 Jul, 2021

Difficulty: Easy