|
Given an array arr[], the task is to minimize the sum of minimum and second minimum elements from all possible triplets. One element can be a part of exactly one triplet.
Input: arr[] = {1, 2, 4, 6, 7, 8, 3}, N = 7
Output: 10
Explanation: Here two triplets are formed as the size of arr[] is 7 and 7/3 = 2.
Triplet 1 – {1, 6, 3} -> Two minimum elements are 1 and 3.
Triplet 2 – {2, 4, 8} -> Two minimum elements are 2 and 4.
Hence sum = 1 + 3 + 2 + 4 = 10
Input: arr[] = {5, 7, 3, 8, 9}
Output: 8
Approach: This problem can be solved by using the Greedy Approach. Follow the steps below to solve the given problem.
- Sort the array arr[] in non-decreasing order, so that it gets easier to choose minimum elements in every triplet.
- Initialize a variable say ans = 0, to store the minimum possible answer.
- Traverse arr[] and make every triplet by taking two elements from the left side and one element from the right side.
- Return ans as the final answer.
C++14
#include <bits/stdc++.h>
using namespace std;
int minTriplets(vector<int>& arr, int N)
{
int ans = 0;
sort(arr.begin(), arr.end());
for (int i = 0, j = N - 1;
i + 1 < j;
i += 2, j--) {
ans += arr[i];
ans += arr[i + 1];
}
return ans;
}
int main()
{
int N = 7;
vector<int> arr = { 1, 2, 4, 6, 7, 8, 3 };
cout << minTriplets(arr, N);
}
|
Java
import java.util.*;
public class GFG
{
static int minTriplets(int []arr, int N)
{
int ans = 0;
Arrays.sort(arr);
for (int i = 0, j = N - 1;
i + 1 < j;
i += 2, j--) {
ans += arr[i];
ans += arr[i + 1];
}
return ans;
}
public static void main(String args[])
{
int N = 7;
int []arr = { 1, 2, 4, 6, 7, 8, 3 };
System.out.print(minTriplets(arr, N));
}
}
|
Python3
def minTriplets (arr, N) :
ans = 0
arr.sort()
i = 0
j = N - 1
while( i + 1 < j):
ans += arr[i]
ans += arr[i + 1]
i += 2
j -= 1
return ans
N = 7
arr = [1, 2, 4, 6, 7, 8, 3]
print(minTriplets(arr, N))
|
C#
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
static int minTriplets(int []arr, int N)
{
int ans = 0;
Array.Sort(arr);
for (int i = 0, j = N - 1;
i + 1 < j;
i += 2, j--) {
ans += arr[i];
ans += arr[i + 1];
}
return ans;
}
public static void Main()
{
int N = 7;
int []arr = { 1, 2, 4, 6, 7, 8, 3 };
Console.Write(minTriplets(arr, N));
}
}
|
Javascript
<script>
const minTriplets = (arr, N) => {
let ans = 0;
arr.sort();
for (let i = 0, j = N - 1;
i + 1 < j;
i += 2, j--) {
ans += arr[i];
ans += arr[i + 1];
}
return ans;
}
let N = 7;
let arr = [1, 2, 4, 6, 7, 8, 3];
document.write(minTriplets(arr, N));
</script>
|
Time Complexity: O(N log N)
Auxiliary Space: O(1)
|
