Rearrange array to maximize count of triplets ( i , j , k ) such that arr [ i ] > arr [ j ] < arr [ k ] and i < j < k | C ++ program to implement the above approach ; Function to rearrange the array to maximize the count of triplets ; Sort the given array ; Stores the permutations of the given array ; Stores the index of the given array ; Place the first half of the given array ; Place the last half of the given array ; Stores the count of triplets ; Check the given conditions ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void ctTriplets ( int arr [ ] , int N ) { sort ( arr , arr + N ) ; vector < int > temp ( N ) ; int index = 0 ; for ( int i = 1 ; i < N ; i += 2 ) { temp [ i ] = arr [ index ++ ] ; } for ( int i = 0 ; i < N ; i += 2 ) { temp [ i ] = arr [ index ++ ] ; } int ct = 0 ; for ( int i = 0 ; i < N ; i ++ ) { if ( i > 0 && i + 1 < N ) { if ( temp [ i ] < temp [ i + 1 ] && temp [ i ] < temp [ i - 1 ] ) { ct ++ ; } } } cout << " Count ▁ of ▁ triplets : " << ct << endl ; cout << " Array : " ; for ( int i = 0 ; i < N ; i ++ ) { cout << temp [ i ] << " ▁ " ; } } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 4 , 5 , 6 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; ctTriplets ( arr , N ) ; }