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-
- Sorting:- Sort the array in non-decreasing order and take the first k elements
- 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;
}
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