Rearrange Array such that sum of adjacent sum divided by K is minimum - Coding

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 A_i+ A_{i + 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 = {A₁, A₂, A₃, A₄, A₅}, 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: (A₁+ A₂) + (A₂+ A₃) + (A₃+ A₄) + (A₄+ A₅) = X

As we can see that all the elements excluding (A₁, A₅) are occurring twice in the process of summation. Formally, The sum X is equal to = (A1 + A5) + 2*(A₂, A₃, A₄).

This observation gives us approach that we should put first maximum and second maximum elements at A₁and A₅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>

Output

[7, 3, 4, 5, 5, 1, 6]

Time Complexity: O(N * log(N))
Auxiliary Space: O(1)

Reffered: https://www.geeksforgeeks.org

Arrays

Related
Construct a sorted Array such that setbit in bitwise XOR of any pair is even
Alone in Couple
Minimize subsequence multiplication to convert Array sum to be power of 2
Check if Array has at least M non-overlapping Subarray with gcd G
Maximize height of tower using elements from one of the given Subarrays

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	12