1.
Introduction
1.1.
Problem Statement
1.2.
Sample examples
2.
Approach
2.1.
Steps of algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
4.
Key Takeaways
Last Updated: Mar 27, 2024

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

Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems

## 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;
}``````

Output:

``21``

#### 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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Q1. Is STL's sort stable?

Ans: Introsort is typically used by the sort() function. As a result, sort() may or may not preserve the physical order of semantically equivalent values. Mergesort is usually used by the stable sort() function. As a result, stable sort() guarantees that the physical order of semantically equivalent values is preserved.

Q2. What is the C++ STL sort's asymptotic complexity?

Ans: The sorting algorithm is not specified in the language standard and may vary between implementations, but the function's worst-case asymptotic complexity is: when applied to a range of N elements, a call to sort must perform O(N log N) comparisons.

Q3. In C++, how do you find the smallest value in an array?

Ans: One variable, minElement, should be set to the first element of the input array. Traverse the input array from index 0 to N -1 using a loop and compare each element to minElement. Update minElement with the current element if the current element is less than minElement.

## Key Takeaways

This article discussed palindrome and the approach to minimize the sum of minimum and second minimum elements from all possible triplets with examples for a better understanding and its C++ code.

Also Read - Selection Sort in C

If you are a beginner, interested in coding and want to learn DSA, you can look for our guided path for DSA, which is free!