Find minimum product among all combinations of triplets in an array

Posted in

Find minimum product among all combinations of triplets in an array
maazbinasad

Maaz Bin Asad
Last updated on July 20, 2024

    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:

    Leave a Comment on this Post

    0 Comments