Given an array of n integers and a number m, find the maximum possible difference between two sets of m elements chosen from given array.
Examples:
Input : arr[] = 1 2 3 4 5
m = 4
Output : 4
The maximum four elements are 2, 3,
4 and 5. The minimum four elements are
1, 2, 3 and 4. The difference between
two sums is (2 + 3 + 4 + 5) - (1 + 2
+ 3 + 4) = 4
Input : arr[] = 5 8 11 40 15
m = 2
Output : 42
The difference is (40 + 15) - (5 + 8)
The idea is to first sort the array, then find sum of first m elements and sum of last m elements. Finally return difference between two sums.
Implementation:
CPP
// C++ program to find difference// between max and min sum of array#include <bits/stdc++.h>using namespace std;// utility functionint find_difference(int arr[], int n, int m){ int max = 0, min = 0; // sort array sort(arr, arr + n); for (int i = 0, j = n - 1; i < m; i++, j--) { min += arr[i]; max += arr[j]; } return (max - min);}// Driver codeint main(){ int arr[] = { 1, 2, 3, 4, 5 }; int n = sizeof(arr) / sizeof(arr[0]); int m = 4; cout << find_difference(arr, n, m); return 0;} |
Java
// Java program to find difference// between max and min sum of arrayimport java.util.Arrays;class GFG { // utility function static int find_difference(int arr[], int n, int m) { int max = 0, min = 0; // sort array Arrays.sort(arr); for (int i = 0, j = n - 1; i < m; i++, j--) { min += arr[i]; max += arr[j]; } return (max - min); } // Driver program public static void main(String arg[]) { int arr[] = { 1, 2, 3, 4, 5 }; int n = arr.length; int m = 4; System.out.print(find_difference(arr, n, m)); }}// This code is contributed by Anant Agarwal. |
Python3
# Python program to# find difference # between max and# min sum of arraydef find_difference(arr, n, m): max = 0; min = 0 # sort array arr.sort(); j = n-1 for i in range(m): min += arr[i] max += arr[j] j = j - 1 return (max - min) # Driver codeif __name__ == "__main__": arr = [1, 2, 3, 4, 5] n = len(arr) m = 4 print(find_difference(arr, n, m)) # This code is contributed by# Harshit Saini |
C#
// C# program to find difference// between max and min sum of arrayusing System;class GFG { // utility function static int find_difference(int[] arr, int n, int m) { int max = 0, min = 0; // sort array Array.Sort(arr); for (int i = 0, j = n - 1; i < m; i++, j--) { min += arr[i]; max += arr[j]; } return (max - min); } // Driver program public static void Main() { int[] arr = { 1, 2, 3, 4, 5 }; int n = arr.Length; int m = 4; Console.Write(find_difference(arr, n, m)); }}// This code is contributed by nitin mittal |
PHP
<?php// PHP program to find difference// between max and min sum of array// utility functionfunction find_difference($arr, $n, $m){ $max = 0; $min = 0; // sort array sort($arr); sort( $arr,$n); for($i = 0, $j = $n - 1; $i <$m; $i++, $j--) { $min += $arr[$i]; $max += $arr[$j]; } return ($max - $min);}// Driver code{ $arr = array(1, 2, 3, 4, 5); $n = sizeof($arr) / sizeof($arr[0]); $m = 4; echo find_difference($arr, $n, $m); return 0;}// This code is contributed by nitin mittal.?> |
Javascript
<script>// JavaScript program to find difference// between max and min sum of array// utility function function find_difference(arr, n, m) { let max = 0, min = 0; // sort array arr.sort(); for (let i = 0, j = n - 1; i < m; i++, j--) { min += arr[i]; max += arr[j]; } return (max - min); }// Driver Code let arr = [ 1, 2, 3, 4, 5 ]; let n = arr.length; let m = 4; document.write(find_difference(arr, n, m)); // This code is contributed by splevel62.</script> |
Output
4
Time Complexity : O(n Log n)
Auxiliary Space : O(1)
We can optimize the above solution using more efficient approaches discussed in below post.
k largest(or smallest) elements in an array | added Min Heap method
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!
