Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Some Examples
2.
Approach
2.1.
Algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What is a Priority Queue?
3.2.
How can we find k-minimum integers using the heap method?
3.3.
Is a priority queue the same as a heap?
4.
Conclusion
Last Updated: Mar 27, 2024
Easy

Minimum product of k integers in an array of positive Integers

Author Prerna Tiwari
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

In this blog, we will be finding the minimum product of k integers in an array of positive Integers. So, let’s get started by introducing the array.

An array is a data structure that holds a collection of elements. These elements are typically all of the same data type, such as an integer or string. In computer programs, arrays are commonly used to organize data so that a related set of values can be easily sorted or searched.

Problem Statement

Ninja has an array of size N. After giving the array. He said he wanted to find the minimum product of k integers in an array of positive Integers. But, the problem is that he cannot do it by himself because he is busy giving training to his student. Can you help him in finding the minimum product of k integers?

Some Examples

Input: 

arr[]= {152, 194, 72, 897, 123, 554, 975}, k = 2  

Output: 

product = 8856 

 

Explanation: We get the minimum product after multiplying 72 and 123.    


Input: 

arr[] = {17, 2, 15, 37, 5, 160}, k = 4  

Output: 

product = 2550 

 

Explanation: We get the minimum product after multiplying 2, 5, 15, and 17.

Approach

We can solve this problem of the minimum product of k integers in an array of positive integers in a very simple way. The idea behind the approach is to first find the k smallest integers and then multiply them.

The output will be the multiplication of the k integers.

Algorithm


Step 1:- As discussed in the approach, we need to find k smallest integers 

For this, we can use a number of approaches. Some of them are-

  1. Sorting:- Sort the array in non-decreasing order and take the first k elements
  2. Heap-based approach:- Here, we can find the k smallest integers by inserting array elements into a min-heap and then taking the top k elements.

 

Step2:- Find the product of the numbers obtained in Step 1 and print it.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

int minProductOfInt(vector<int> &arr, int k)
{
    sort(arr.begin(), arr.end());
    int minProductofKintegers = 1;

    for (int i = 0; i < k; i++)
    {
        minProductofKintegers *= arr[i];
    }

    return minProductofKintegers;
}
int main()
{

    vector<int> arr{152, 194, 72, 897, 123, 554, 975};
    int k = 3;

    int minProductofKintegers = minProductOfInt(arr, k);

    cout << minProductofKintegers << endl;

    return 0;
}
You can also try this code with Online C++ Compiler
Run Code

 

Output 

product = 1346112

 

Complexity Analysis

Time Complexity 

Since we are sorting, and sorting is performed in O(N*log N) time complexity, therefore the overall time complexity of the above program will be O(N*log N) where N is the size of the array.

Space Complexity 

Since no extra space is being used the space complexity will be O(1).

Also see,  Rabin Karp Algorithm

Frequently Asked Questions

What is a Priority Queue?

Items in the Priority queue are ordered by key value so that the item with the lowest key value is at the front and the item with the highest key value is at the back, or vice versa. As a result, we assign priority to each item based on its key value.

How can we find k-minimum integers using the heap method?

We can insert array elements into a min-heap and then take top k elements.

priority_queue<int, vector<int>, greater<int> > minheap;
for (int i = 0; i < n; i++)
minheap.push(arr[i]);

while (minheap.empty() == false && k>0) {
cout<<minheap.top()<<endl;
minheap.pop();
k--;
}
You can also try this code with Online C++ Compiler
Run Code

Is a priority queue the same as a heap?

The priority queue is built on a queue data structure that functions as a queue with a priority function. The heap is a tree data structure that is used to sort data in a specific order based on an algorithm.

Conclusion

In this blog, we have learned to find the minimum product of k integers in an array of positive Integers. We started with introducing array, problem statement, example, approach, and implementation, and finally concluded with time and space complexity.

We hope that this blog has helped you enhance your knowledge of how to find the Minimum product of k integers in an array of positive Integers and if you would like to learn more, check out our other articles on Data Structures.

Recommended Readings:

For peeps out there who want to learn more about Data Structures, Algorithms, Power programming, JavaScript, or any other upskilling, please refer to guided paths on Coding Ninjas Studio. Enroll in our courses, go for mock tests, solve problems available, and interview puzzles. Also, you can put your attention towards interview stuff- interview experiences and an interview bundle for placement preparations. 

Do upvote our blog to help other ninjas grow. 

Happy Coding!

Live masterclass