You are given an array of n elements. You have to divide the given array into two group such that one group consists exactly k elements and second group consists rest of elements. Your result must be maximum possible difference of sum of elements of these two group.
Examples:
Input : arr[n] = {1, 5, 2, 6, 3} , k = 2
Output : Maximum Difference = 11
Explanation : group1 = 1+2 , group2 = 3+5+6
Maximum Difference = 14 - 3 = 11
Input : arr[n] = {1, -1, 3, -2, -3} , k = 2
Output : Maximum Difference = 10
Explanation : group1 = -1-2-3 , group2 = 1+3
Maximum Difference = 4 - (-6) = 10
For finding the maximum group difference we have two possibilities. For the first case k-smallest elements belongs to one group and rest elements to other group. For second case k-largest elements belongs to one group and rest elements to other group.
So, first of all sort the whole array and find group difference for both cases explained as above and then finally find the maximum difference among them.
Algorithm :
sort the arrayfind sum of whole array
case-1 -> find sum of first k-smallest elements
-> differece1 = abs( arraySum - 2*k_Smallest)
case-2 -> find sum of first k-largest elements
-> differece2 = abs( arraySum - 2*k_largest)
print max(difference1, difference2)
Implementation:
C++
// CPP to find maximum group difference #include<bits/stdc++.h> using namespace std; // utility function for array sum long long int arraySum(int arr[], int n) { long long int sum = 0; for (int i=0; i<n; i++) sum = sum + arr[i]; return sum; } // function for finding // maximum group difference of array long long int maxDiff (int arr[], int n, int k) { // sort the array sort(arr, arr+n); // find array sum long long int arraysum = arraySum(arr, n); // difference for k-smallest // diff1 = (arraysum-k_smallest)-k_smallest long long int diff1 = abs(arraysum - 2*arraySum(arr, k)); // reverse array for finding sum of 1st k-largest reverse(arr, arr+n); // difference for k-largest // diff2 = (arraysum-k_largest)-k_largest long long int diff2 = abs(arraysum - 2*arraySum(arr, k)); // return maximum difference value return(max(diff1,diff2)); } // driver program int main() { int arr[] = {1, 7, 4, 8, -1, 5, 2, 1}; int n = sizeof(arr)/sizeof(arr[0]); int k = 3; cout << "Maximum Difference = " << maxDiff(arr,n,k); return 0; } |
Java
// java to find maximum group difference import java.util.Arrays; public class GFG { // utility function for array sum static long arraySum(int arr[], int n) { long sum = 0; for (int i = 0; i < n; i++) sum = sum + arr[i]; return sum; } // function for finding maximum group // difference of array static long maxDiff (int arr[], int n, int k) { // sort the array Arrays.sort(arr); // find array sum long arraysum = arraySum(arr, n); // difference for k-smallest // diff1 = (arraysum-k_smallest)-k_smallest long diff1 = Math.abs(arraysum - 2 * arraySum(arr, k)); // reverse array for finding sum of // 1st k-largest int end = arr.length - 1; int start = 0; while (start < end) { int temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; start++; end--; } // difference for k-largest // diff2 = (arraysum-k_largest)-k_largest long diff2 = Math.abs(arraysum - 2 * arraySum(arr, k)); // return maximum difference value return(Math.max(diff1, diff2)); } public static void main(String args[]) { int arr[] = {1, 7, 4, 8, -1, 5, 2, 1}; int n = arr.length; int k = 3; System.out.println("Maximum Difference = " + maxDiff(arr, n, k)); } } // This code is contributed by Sam007. |
Python3
# Python3 to find maximum group difference # utility function for array sum def arraySum(arr, n): sum = 0 for i in range(n): sum = sum + arr[i] return sum # function for finding # maximum group difference of array def maxDiff (arr, n, k): # sort the array arr.sort() # find array sum arraysum = arraySum(arr, n) # difference for k-smallest # diff1 = (arraysum-k_smallest)-k_smallest diff1 = abs(arraysum - 2 * arraySum(arr, k)) # reverse array for finding sum # of 1st k-largest arr.reverse() # difference for k-largest # diff2 = (arraysum-k_largest)-k_largest diff2 = abs(arraysum - 2 * arraySum(arr, k)) # return maximum difference value return(max(diff1, diff2)) # Driver Code if __name__ == "__main__": arr = [1, 7, 4, 8, -1, 5, 2, 1] n = len(arr) k = 3 print ("Maximum Difference =", maxDiff(arr, n, k)) # This code is contributed by ita_c |
C#
// C# to find maximum group difference using System; public class GFG { // utility function for array sum static long arraySum(int []arr, int n) { long sum = 0; for (int i = 0; i < n; i++) sum = sum + arr[i]; return sum; } // function for finding maximum group // difference of array static long maxDiff (int []arr, int n, int k) { // sort the array Array.Sort(arr); // find array sum long arraysum = arraySum(arr, n); // difference for k-smallest // diff1 = (arraysum-k_smallest)-k_smallest long diff1 = Math.Abs(arraysum - 2 * arraySum(arr, k)); // reverse array for finding sum of // 1st k-largest Array.Reverse(arr); // difference for k-largest // diff2 = (arraysum-k_largest)-k_largest long diff2 = Math.Abs(arraysum - 2 * arraySum(arr, k)); // return maximum difference value return(Math.Max(diff1, diff2)); } // Driver program static public void Main () { int []arr = {1, 7, 4, 8, -1, 5, 2, 1}; int n = arr.Length; int k = 3; Console.WriteLine("Maximum Difference = " + maxDiff(arr, n, k)); } } // This Code is contributed by vt_m. |
PHP
<?php // PHP to find maximum group difference // utility function for array sum function arraySum($arr, $n) { $sum = 0; for ($i = 0; $i < $n; $i++) $sum = $sum + $arr[$i]; return $sum; } // function for finding // maximum group difference // of array function maxDiff ($arr, $n, $k) { // sort the array sort($arr); // find array sum $arraysum = arraySum($arr, $n); // difference for k-smallest // diff1 = (arraysum - k_smallest) // - k_smallest $diff1 = abs($arraysum - 2 * arraySum($arr, $k)); // reverse array for finding // sum of 1st k-largest array_reverse($arr); // difference for k-largest // diff2 = (arraysum - k_largest) // - k_largest $diff2 = abs($arraysum - 2 * arraySum($arr, $k)); // return maximum difference value return(max($diff1,$diff2)); } // Driver Code $arr = array(1, 7, 4, 8, -1, 5, 2, 1); $n = count($arr); $k = 3; echo "Maximum Difference = " , maxDiff($arr, $n, $k); // This Code is contributed by vt_m. ?> |
Javascript
<script> // Javascript to find maximum group difference // utility function for array sum function arraySum(arr, n) { var sum = 0; for (var i=0; i<n; i++) sum = sum + arr[i]; return sum; } // function for finding // maximum group difference of array function maxDiff (arr, n, k) { // sort the array arr.sort((a,b)=>a-b); // find array sum var arraysum = arraySum(arr, n); // difference for k-smallest // diff1 = (arraysum-k_smallest)-k_smallest var diff1 = Math.abs(arraysum - 2*arraySum(arr, k)); // reverse array for finding sum of 1st k-largest arr.reverse(); // difference for k-largest // diff2 = (arraysum-k_largest)-k_largest var diff2 = Math.abs(arraysum - 2*arraySum(arr, k)); // return maximum difference value return(Math.max(diff1,diff2)); } // driver program var arr = [1, 7, 4, 8, -1, 5, 2, 1]; var n = arr.length; var k = 3; document.write( "Maximum Difference = " + maxDiff(arr,n,k)); </script> |
Output
Maximum Difference = 25
Time Complexity: O(n log n)
Auxiliary Space: O(1)
Optimizations to above solution :
- We can avoid reversing the array and find sum k elements from end using a different loop.
- We can also find sum of k largest and smallest elements more efficiently using methods discussed in below posts.
K’th Smallest/Largest Element in Unsorted Array | Set 2 (Expected Linear Time)
K’th Smallest/Largest Element in Unsorted Array | Set 3 (Worst Case Linear Time)
This article is contributed by Shivam Pradhan . If you like neveropen and would like to contribute, you can also write an article using write.neveropen.co.za or mail your article to review-team@neveropen.co.za. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
