Minimize the sum of minimum and second minimum elements from all possible triplets

Introduction 

This blog will discuss the problem of finding the minimum possible sum of minimum and second minimum of all possible triplets in an array.

Problem Statement

We are given an array having n elements. Our task is to minimize the sum of minimum and second minimum elements from all possible triplets from the given array. A single element of the given array can only be a part of one triplet.

Sample examples

Input - 1: a[] = [ 4, 5, 6, 3, 1, 7, 9 ]

Output - 1: 13

Explanation: There are only two possible triplets as there are only 7 elements in the given array.

Triplet1: (1, 3, 9)

Triplet2: (4, 5, 7)

Sum of minimum and second minimum elements of all possible triplets = 1 + 3 + 4 + 5

Input - 2: a[] = [ 4, 5, 6, 7, 8 ,9, 1, 2, 3 ]

Output - 2: 21

Explanation: There are 3 possible triplets as there are 9 elements in the given array

Triplet1: (1,2,9)

Triplet2: (3,4,8)

Triplet3: (5,6,7)

Sum of minimum and second minimum elements of all possible triplets = 1 + 2 + 3 + 4 + 5 + 6 = 21

Approach

The idea is very simple, count the possible number of triplets from the given array. Now, as we need to minimize the sum of the minimum and second minimum elements for every possible triplet, we calculate the sum of the first k minimum numbers in the given array where k = 2 * number of possible triplets.

To find the sum of the first k minimum elements in the given array, sort the array in non-decreasing order and find the sum of the first k elements.

Steps of algorithm

• Calculate the possible number of triplets and store it in the possible_triplets variable, where possible_triplets = n/3.
• Declare a variable k and do k = 2 * possible triplets.
• Now, sort the given array, sort(a, a+n).
• Declare a variable ans and initialize it with 0.
• Finally, calculate the sum of the first k elements in the given array and store them in the ans variable.
• Return the value of ans variable.

Let’s understand the above approach with an example: 

Given array:

• possible_triplets = n/3 = 7/3 = 2
• k = 2*possible_triplets = 2*2 = 4
• Now, sort the given array.

• ans = 0
• Calculate the sum of the first k elements.
   

• ans = 1 + 3+ 4 + 5 = 13
   

Finally, return the value of ans variable.

Implementation in C++

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

int minm_sum(int a[], int n)
{
    int possible_triplets = n / 3;  // possible number of triplets

    int k = 2 * possible_triplets; 

    sort(a, a + n);    // sorting the given array

    int ans = 0;

    for (int i = 0; i < k; i++)   //first k minimum elements sum
    {
        ans = ans + a[i];
    }
    return ans;
}

int main()
{
    int a[] = { 4, 5, 6, 8, 7 , 9, 1, 2, 3 }; //given array

    int n = sizeof(a) / sizeof(a[0]);    // size of array

    cout << minm_sum(a, n);

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

21

You can also try this code with Online C++ Compiler

Run Code

Complexity Analysis

Time complexity: We are using the sort function, so the time complexity is O(n*logn), where n is the size of the given array.

Space complexity: O(1) as we have used constant extra space.

Check out this array problem - Merge 2 Sorted Arrays