Given an array a[] of 2*N integers, The task is to make the array a[] of size N i.e, reducing it to half size such that, a[i] = ?(a[j] + a[k]) / N?, 0 < j, k < 2*N – 1. and form the array so that the sum of all the elements of the array a[], will be maximum. Output the maximum sum.
Examples:
Input: arr[] = {3, 5, 10, 8, 4, 7}, N = 3
Output: 12
Explanation: If we form, a[] = {4 + 5, 7+8, 3+10} = {9, 15, 13},
Sum = floor(9/3) + floor(15/3) + floor(13/3) = 3 + 5 + 4 = 12.Input: arr[] = {1, 2}, N = 1
Output: 3
Approach: To solve the problem follow the below idea:
The idea is to pair the elements whose sum (a[i]+a[j])%N > a[i]%N + a[j]%N, for this we have to store a[i]/N for 0<i<2*N-1 and modify a[i] = a[i]%N for finding the remainder. Now we have to from i with j such that a[i] + a[j] >= N [0<(a[i]+a[j])<2N-2], because, we have to take as many extra count that we were losing with floor division.
For this we have to sort the array and initialize pointers i = 2*N-1and j=0, and start forming pairs with last element because it is the greatest, if it cannot form pair with sum ? N then any other pair does not form, we have to from the pairs of available largest element with smallest element such that sum ? N if possible.
Follow the below steps to solve the problem:
- First of all, we have to store the sum of the given array by sum=sum+arr[i]/n and update the value of the array by arr[i]=arr[i]%n.
- After that, sort the array.
- Then, by using the two-pointers approach, find the pairs with a sum greater than or equal to n.
- Then return the sum.
Below is the implementation of the above approach:
C++
// C++ code for above approach#include <bits/stdc++.h>using namespace std;// Function to form the array and return// maximum possible sumint solve(int* a, int n){ // Initialize result int Sum = 0; for (int i = 0; i < 2 * n; i++) { Sum = Sum + a[i] / n; a[i] = a[i] % n; } // Sort the array sort(a, a + 2 * n); // Initialize pointers int i = 2 * n - 1; int j = 0; // Find pairs with sum greater // than or equal to N while (i > j) { if (a[i] + a[j] >= n) { Sum++; i--; j++; } else { j++; } } // Return maximum possible sum return Sum;}// Driver Codeint main(){ int arr[] = { 3, 5, 10, 8, 4, 7 }; int N = 3; // Function Call cout << solve(arr, N) << endl; return 0;} |
Java
// Java code for above approachimport java.io.*;import java.util.*;class GFG { // Function to form the array and return // maximum possible sum static int solve(int[] a, int n) { // Initialize result int Sum = 0; for (int i = 0; i < 2 * n; i++) { Sum = Sum + a[i] / n; a[i] = a[i] % n; } // Sort the array Arrays.sort(a); // Initialize pointers int i = 2 * n - 1; int j = 0; // Find pairs with sum greater // than or equal to N while (i > j) { if (a[i] + a[j] >= n) { Sum++; i--; j++; } else { j++; } } // Return maximum possible sum return Sum; } public static void main(String[] args) { int[] arr = { 3, 5, 10, 8, 4, 7 }; int N = 3; // Function call System.out.println(solve(arr, N)); }}// This code is contributed by lokeshmvs21. |
Python3
# Python code for above approach# Function to form the array and return# maximum possible sumdef solve(a, n): # Initialize result Sum = 0 for i in range(2 * n): Sum = Sum + int(a[i] / n) a[i] = a[i] % n # Sort the array a.sort() # Initialize pointers i = 2 * n - 1 j = 0 # Find pairs with sum greater # than or equal to N while i > j: if a[i] + a[j] >= n: Sum += 1 i -= 1 j += 1 else: j += 1 # Return maximum possible sum return Sum# Driver Codearr = [3, 5, 10, 8, 4, 7]N = 3# Function callprint(solve(arr, N))# This code is contributed by Tapesh(tapeshdua420) |
C#
// C# codeusing System;public class GFG { // Function to form the array and return // maximum possible sum public static int solve(int[] a, int n) { // Initialize result int Sum = 0; for (int k = 0; k < 2 * n; k++) { Sum = Sum + (int)(a[k] / n); a[k] = a[k] % n; } // Sort the array Array.Sort(a, 0, 2 * n); // Initialize pointers int i = 2 * n - 1; int j = 0; // Find pairs with sum greater // than or equal to N while (i > j) { if (a[i] + a[j] >= n) { Sum++; i--; j++; } else { j++; } } // Return maximum possible sum return Sum; } static public void Main() { int[] arr = { 3, 5, 10, 8, 4, 7 }; int N = 3; // Function Call Console.WriteLine(solve(arr, N)); }}// This code is contributed by ksam24000. |
Javascript
// Javascript code for above approach// Function to form the array and return// maximum possible sumfunction solve(a, n) { // Initialize result var Sum = 0; for (var i = 0; i < 2 * n; i++) { Sum += parseInt(a[i] / n); a[i] = a[i] % n; } // Sort the array a.sort(); // Initialize pointers var i = 2 * n - 1; var j = 0; // Find pairs with sum greater // than or equal to N while (i > j) { if (a[i] + a[j] >= n) { Sum++; i--; j++; } else { j++; } } // Return maximum possible sum return Sum;}// Driver Codevar arr = [3, 5, 10, 8, 4, 7];var N = 3;// Function callconsole.log(solve(arr, N));// This code is contributed by Tapesh(tapeshdua420) |
12
Time Complexity: O(N * log N)
Auxiliary Space: O(1)
Related Articles:
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
