Maximum difference between group of k-elements and rest of the array.

0 0 6 minutes read

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 zambiatek and would like to contribute, you can also write an article using write.zambiatek.com or mail your article to review-team@zambiatek.com. See your article appearing on the zambiatek main page and help other Geeks.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!