Given an array arr[] of 2N integers, where N is any positive integer. The task is to divide the array into N pairs such that the pair sum minimizes the maximum sum of a pair i.e., the pair sums for this partition are minimum of the maximum pair sum of all possible partitions of the array.
Examples:
Input : arr[] = {6, 9, 4, 10} Output : (4,10)(6,9) Explanation: Possible Pairs : (9,10)(4,6) sum = (19)(10) maximum pair sum = 19 (6,10)(4,9) sum = (16)(15) maximum pair sum = 16 (4,10)(6,9) sum = (14)(17) maximum pair sum = 14 Thus partition (4,10)(6,9) has the minimum of the maximum pair sum of all possible partitions. Input : arr[] = {10, 7, 2, 6} Output : (2,10)(6,7)
RECOMMENDED: Java is a good programming to start with
Approach: Use greedy approach to form the pairs that will result in the minimum of maximum pair sum of all possible partitions. Following steps will help in solving this problem:
- Sort the array.
- Form N pairs using first and last element, second and second last and so on.
- Print the N pairs formed.
Below is the implementation of the above approach:
// Java program to divide the array // into N pairs such that it has minimum of // maximum pair sum of possible partitions import java.io.*; import java.util.*; import java.lang.*; public class Cpp { // Function to divide the array into N pairs // such that it has minimum of maximum pair sum possible static void divideArray(int[] arr, int len) { // sort the array Arrays.sort(arr); for (int i = 0; i < len / 2; i++) { System.out.print("(" + arr[i] + "," + arr[len-1-i] + ")"); } } // Driver code public static void main(String args[]) { int[] arr = {6, 9, 4, 10}; // length of the array int len = arr.length; divideArray(arr, len); } }
Output:
(4,10)(6,9)
Time complexity: O(nlogn), due to sorting.
Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.