Given an integer array arr[] of length N and an integer K, the task is to rearrange the elements of arr[] in such a way that the value of the total sum of Ai + Ai + 1 divided by K is minimized for all (1 ≤ i ≤ N – 1). If there are multiple arrangements, then print any of them.
Examples:
Input: N = 5, arr[] = {4, 7, 1}, K = 3
Output: arr[] = {7, 1, 4}
Explanation: Total Sum is: (7 + 1) + (1 + 4) = 8 + 5 = 13 / 3 = 4.33,
It can be verified that no other arrangement of arr[] elements
can give value of operation less than 4.33.Input: N = 2, arr[] = {5, 2}, K = 1
Output: arr[] = {5, 2}
Explanation: No matters what the arrangement of elements is,
value of total sum will always remain 7.
Approach: Implement the idea below to solve the problem:
Obtain first maximum and second maximum elements from the whole arr[] and place them at first and last index of the arr[]. Arrangement of rest of the elements doesn’t matter.
Proof of approach:
Consider an arr[] having elements = {A1, A2, A3, A4, A5}, K = Z
Then, Value of operation let’s say Y = (sum of arr[] / Z)
Y will be smallest when sum of arr[] will be smallest because they are directly proportional to each other. So our main goal is to make the smallest possible sum of arr[].Now, Sum of the arr[] according to given conditions: (A1 + A2) + (A2 + A3) + (A3 + A4) + (A4 + A5) = X
As we can see that all the elements excluding (A1, A5) are occurring twice in the process of summation. Formally, The sum X is equal to = (A1 + A5) + 2*(A2, A3, A4).
This observation gives us approach that we should put first maximum and second maximum elements at A1 and A5 So that sum can be minimized, Arrangement of rest of the elements doesn’t matter because they all are occurring twice.
Follow the steps mentioned below to implement the idea:
- Traverse through the array and find the maximum and the second maximum value.
- Place those two at the first and the last position.
- Arrange the rest of the elements in any order.
- Return the newly formed array as the required answer.
Below is the implementation for the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
// Function which is called in main()
void ArrangeElements(int* arr,int N)
{
// Sorting the array in increasing
// order by inbuilt sort() function
// in Arrays class
sort(arr,arr+N);
// Replacing first max element
// with element at starting of arr[]
int temp1 = arr[N - 1];
arr[N - 1] = arr[0];
arr[0] = temp1;
// Replacing second max element
// with element at last of arr[]
int temp2 = arr[N - 1];
arr[N - 1] = arr[N - 2];
arr[N - 2] = temp2;
}
// Driver Function
int main()
{
int N = 7;
int arr[N] = { 5, 1, 6, 7, 5, 4, 3 };
// Function call
ArrangeElements(arr,N);
// Printing the arr[]
for (int i = 0; i < N; i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;
return 0;
}
// This code is contributed by akashish__
Java
// Java code to implement the approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
// Driver Function
public static void main(String[] args)
throws java.lang.Exception
{
int n = 7;
int[] arr = { 5, 1, 6, 7, 5, 4, 3 };
int k = 5;
// Function call
ArrangeElements(arr);
// Printing the arr[]
System.out.println(Arrays.toString(arr));
}
// Function which is called in main()
static void ArrangeElements(int[] arr)
{
// Sorting the array in increasing
// order by inbuilt sort() function
// in Arrays class
Arrays.sort(arr);
// Replacing first max element
// with element at starting of arr[]
int temp1 = arr[arr.length - 1];
arr[arr.length - 1] = arr[0];
arr[0] = temp1;
// Replacing second max element
// with element at last of arr[]
int temp2 = arr[arr.length - 1];
arr[arr.length - 1] = arr[arr.length - 2];
arr[arr.length - 2] = temp2;
}
}
Python3
class GFG :
# Driver Function
@staticmethod
def main( args) :
n = 7
arr = [5, 1, 6, 7, 5, 4, 3]
k = 5
# Function call
GFG.ArrangeElements(arr)
# Printing the arr[]
print(arr)
# Function which is called in main()
@staticmethod
def ArrangeElements( arr) :
# Sorting the array in increasing
# order by inbuilt sort() function
# in Arrays class
arr.sort()
# Replacing first max element
# with element at starting of arr[]
temp1 = arr[len(arr) - 1]
arr[len(arr) - 1] = arr[0]
arr[0] = temp1
# Replacing second max element
# with element at last of arr[]
temp2 = arr[len(arr) - 1]
arr[len(arr) - 1] = arr[len(arr) - 2]
arr[len(arr) - 2] = temp2
if __name__=="__main__":
GFG.main([])
# This code is contributed by aadityaburujwale.
C#
// Include namespace system
using System;
using System.Linq;
using System.Collections;
public class GFG
{
// Driver Function
public static void Main(String[] args)
{
int[] arr = {5, 1, 6, 7, 5, 4, 3};
// Function call
GFG.ArrangeElements(arr);
// Printing the arr[]
Console.WriteLine(string.Join(", ",arr));
}
// Function which is called in main()
static void ArrangeElements(int[] arr)
{
// Sorting the array in increasing
// order by inbuilt sort() function
// in Arrays class
Array.Sort(arr);
// Replacing first max element
// with element at starting of arr[]
var temp1 = arr[arr.Length - 1];
arr[arr.Length - 1] = arr[0];
arr[0] = temp1;
// Replacing second max element
// with element at last of arr[]
var temp2 = arr[arr.Length - 1];
arr[arr.Length - 1] = arr[arr.Length - 2];
arr[arr.Length - 2] = temp2;
}
}
// This code is contributed by aadityaburujwale..
Javascript
<script>
function ArrangeElements(arr, N) {
// Sorting the array in increasing
// order by inbuilt sort() function
// in Arrays class
arr.sort();
// Replacing first max element
// with element at starting of arr[]
let temp1 = arr[N - 1];
arr[N - 1] = arr[0];
arr[0] = temp1;
// Replacing second max element
// with element at last of arr[]
let temp2 = arr[N - 1];
arr[N - 1] = arr[N - 2];
arr[N - 2] = temp2;
}
// Driver Function
let N = 7;
let arr = [5, 1, 6, 7, 5, 4, 3];
// Function call
ArrangeElements(arr, N);
// Printing the arr[]
console.log(arr);
// This code is contributed by akashish__
</script>
[7, 3, 4, 5, 5, 1, 6]
Time Complexity: O(N * log(N))
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!