# Minimum product of k integers in an array of positive Integers

Given an array of n positive integers. We are required to write a program to print the minimum product of k integers of the given array.

Examples:

```Input : 198 76 544 123 154 675
k = 2
Output : 9348
We get minimum product after multiplying
76 and 123.

Input : 11 8 5 7 5 100
k = 4
Output : 1400
```

The idea is simple, we find the smallest k elements and print multiplication of them. In below implementation, we have used simple Heap based approach where we insert array elements into a min heap and then find product of top k elements.

## C++

 `// CPP program to find minimum product of ` `// k elements in an array ` `#include ` `using` `namespace` `std; ` ` `  `int` `minProduct(``int` `arr[], ``int` `n, ``int` `k) ` `{ ` `    ``priority_queue<``int``, vector<``int``>, greater<``int``> > pq; ` `    ``for` `(``int` `i = 0; i < n; i++) ` `        ``pq.push(arr[i]); ` ` `  `    ``int` `count = 0, ans = 1; ` ` `  `    ``// One by one extract items from max heap ` `    ``while` `(pq.empty() == ``false` `&& count < k) { ` `        ``ans = ans * pq.top(); ` `        ``pq.pop(); ` `        ``count++; ` `    ``} ` ` `  `    ``return` `ans; ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `arr[] = {198, 76, 544, 123, 154, 675}; ` `    ``int` `k = 2; ` `    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr); ` `    ``cout << ``"Minimum product is "` `         ``<< minProduct(arr, n, k); ` `    ``return` `0; ` `} `

## Python3

 `# Python3 program to find minimum ` `# product of k elements in an array ` `import` `math  ` `import` `heapq ` ` `  `def` `minProduct(arr, n, k): ` ` `  `    ``heapq.heapify(arr) ` `    ``count ``=` `0` `    ``ans ``=` `1` ` `  `    ``# One by one extract  ` `    ``# items from min heap ` `    ``while` `( arr ) ``and` `count < k: ` `        ``x ``=` `heapq.heappop(arr) ` `        ``ans ``=` `ans ``*` `x ` `        ``count ``=` `count ``+` `1` `     `  `    ``return` `ans; ` ` `  `# Driver method ` `arr ``=` `[``198``, ``76``, ``544``, ``123``, ``154``, ``675``] ` `k ``=` `2` `n ``=` `len``(arr) ` `print` `(``"Minimum product is"``, ` `       ``minProduct(arr, n, k)) `

Output:

```Minimum product is 9348
```

Time Complexity : O(n * log n)

Note that the above problem can be solved in O(n) time using methods discussed here and here.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

This article is attributed to GeeksforGeeks.org

code

load comments