You are given an array W[1], W[2], …, W[N]. Choose K numbers among them such that the absolute difference between the sum of chosen numbers and the sum of remaining numbers is as large as possible.
Examples :
Input : arr[] = [8, 4, 5, 2, 10]
k = 2
Output: 17Input : arr[] = [1, 1, 1, 1, 1, 1, 1, 1]
k = 3
Output: 2
There are two possibilities to get the desired answer. These two are: Choose k largest numbers or Choose k smallest numbers. Choose the best-suited option which fits according to the given values. This is because there are some cases in which the sum of smallest k numbers can be greater than rest of the array and there are some cases in which the sum of largest k numbers can be greater than rest of the sum of the numbers.
Approach :
- Sort the given array.
- Get the sum of all the numbers of the array and store it in sum
- Get the sum of first k numbers of the array and store it in sum1
- Get the sum of last k numbers of the array and store it in sum2
- Output the result which is : max(abs(S1-(S-S1)), abs(S2-(S-S2)))
Implementation:
C++
// C++ Program to find maximum weight // difference #include <iostream> #include <algorithm> using namespace std; // return the max value of two numbers int solve(int array[], int n, int k) { // sort the given array sort(array, array + n); // Initializing the value to 0 int sum = 0, sum1 = 0, sum2 = 0; // Getting the sum of the array for (int i = 0; i < n; i++) { sum += array[i]; } // Getting the sum of smallest k elements for (int i = 0; i < k; i++) { sum1 += array[i]; } sort(array, array+n, greater<int>()); // Getting the sum of k largest elements for (int i = 0; i < k; i++) { sum2 += array[i]; } // Returning the maximum possible difference. return max(abs(sum1 - (sum - sum1)), abs(sum2 - (sum - sum2))); } // Driver function int main() { int k = 2; int array[] = { 8, 4, 5, 2, 10 }; // calculate the numbers of elements in the array int n = sizeof(array) / sizeof(array[0]); // call the solve function cout << solve(array, n, k); return 0; } |
Java
// JAVA Code for Maximum Weight Difference import java.util.*; class GFG { public static int solve(int array[], int n, int k) { // sort the given array Arrays.sort(array); // Initializing the value to 0 int sum = 0, sum1 = 0, sum2 = 0; // Getting the sum of the array for (int i = 0; i < n; i++) { sum += array[i]; } // Getting the sum of first k elements for (int i = 0; i < k; i++) { sum1 += array[i]; } // Getting the sum of (n-k) elements for (int i = k; i < n; i++) { sum2 += array[i]; } // Returning the maximum possible difference. return Math.max(Math.abs(sum1 - (sum - sum1)), Math.abs(sum2 - (sum - sum2))); } /* Driver program to test above function */ public static void main(String[] args) { int k = 2; int array[] = { 8, 4, 5, 2, 10 }; // calculate the numbers of elements // in the array int n = array.length; // call the solve function System.out.print(solve(array, n, k)); } } // This code is contributed by Arnav Kr. Mandal. |
Python
def solve(array, k): # Sorting array array.sort() # Getting the sum of all the elements s = sum(array) # Getting the sum of smallest k elements s1 = sum(array[:k]) # Getting the sum greatest k elements array.sort(reverse=True) s2 = sum(array[:k]) # Returning the maximum possible difference return max(abs(s1-(s-s1)), abs(s2-(s-s2))) # Driver function k = 2array =[8, 4, 5, 2, 10] print(solve(array, k)) |
C#
// C# Code for Maximum Weight Difference using System; class GFG { public static int solve(int []array, int n, int k) { // sort the given array Array.Sort(array); // Initializing the value to 0 int sum = 0, sum1 = 0, sum2 = 0; // Getting the sum of the array for (int i = 0; i < n; i++) { sum += array[i]; } // Getting the sum of first k elements for (int i = 0; i < k; i++) { sum1 += array[i]; } // Getting the sum of (n-k) elements for (int i = k; i < n; i++) { sum2 += array[i]; } // Returning the maximum possible difference. return Math.Max(Math.Abs(sum1 - (sum - sum1)), Math.Abs(sum2 - (sum - sum2))); } /* Driver program to test above function */ public static void Main() { int k = 2; int []array = { 8, 4, 5, 2, 10 }; // calculate the numbers of elements // in the array int n = array.Length; // call the solve function Console.WriteLine(solve(array, n, k)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP Program to find maximum weight // difference // return the max value of two numbers function maxi($a, $b) { if ($a > $b) { return $a; } else { return $b; } } function solve(&$arr, $n, $k) { // sort the given array sort($arr); // Initializing the value to 0 $sum = 0; $sum1 = 0; $sum2 = 0; // Getting the sum of the array for ($i = 0; $i < $n; $i++) { $sum += $arr[$i]; } // Getting the sum of first k elements for ($i = 0; $i < $k; $i++) { $sum1 += $arr[$i]; } // Getting the sum of (n-k) elements for ($i = $k; $i < $n; $i++) { $sum2 += $arr[$i]; } // Returning the maximum possible difference. return maxi(abs($sum1 - ($sum - $sum1)), abs($sum2 - ($sum - $sum2))); } // DriverCode $k = 2; $arr = array(8, 4, 5, 2, 10 ); // calculate the numbers of // elements in the array $n = sizeof($arr); // call the solve function echo (solve($arr, $n, $k)); // This code is contributed // by Shivi_Aggarwal ?> |
Javascript
<script> // JavaScript Code for Maximum Weight Difference function solve(array, n, k) { // sort the given array array.sort(function(a, b){return a - b}); // Initializing the value to 0 let sum = 0, sum1 = 0, sum2 = 0; // Getting the sum of the array for (let i = 0; i < n; i++) { sum += array[i]; } // Getting the sum of first k elements for (let i = 0; i < k; i++) { sum1 += array[i]; } // Getting the sum of (n-k) elements for (let i = k; i < n; i++) { sum2 += array[i]; } // Returning the maximum possible difference. return Math.max(Math.abs(sum1 - (sum - sum1)), Math.abs(sum2 - (sum - sum2))); } let k = 2; let array = [ 8, 4, 5, 2, 10 ]; // calculate the numbers of elements // in the array let n = array.length; // call the solve function document.write(solve(array, n, k)); </script> |
Output
17
Time Complexity: O(n log n), where n is the length of the array.
Auxiliary Space: O(1)
This article is contributed by Rishabh Bansal. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. 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!
