P roblem
Find the minimum product of any three triplets in an array.
Sample Input
[1, 2, 3, 4]
Sample Output
6
Approach
We can sort the array and find the minimum product of the first 3 numbers and the product of the last two numbers and the first number. This is because a large number multiplied by a negative number will give a large negative number. This approach takes O(NlogN) time.
C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
intsolve(vector<int> arr)
{
sort(arr.begin(), arr.end());
int n = arr.size();
return min(arr[n-1] * arr[n-2] * arr[0], arr[0] * arr[1] * arr[2]);
}
intmain()
{
vector<int> arr = { 2, -1, 3, -5, 1 };
int min = solve(arr);
cout << "Minimum product is " << min;
}
Output
Minimum product is -30
Java
import java.util.Arrays;
classMain
{
publicstaticintsolve(int[] arr)
{
int n = arr.length;
Arrays.sort(arr);
return Integer.min(arr[n-1] * arr[n-2] * arr[0], arr[0] * arr[1] * arr[2]);
}
publicstaticvoidmain(String[] args)
{
int[] arr = { 1, -1, 3, 5, 10 };
int min = solve(arr);
System.out.print("Minimum product is " + min);
}
}
Output
Minimum product is -50
Python
def solve(arr):
n = len(arr)
arr.sort()
return min(arr[n-1] * arr[n-2] * arr[0], arr[0] * arr[1] * arr[2])
arr = [1, -1, 2, 9]
min = solve(arr)
print("Minimum product is", min)
Output
Minimum product is -18
People are also reading:
