Given a sorted array arr[] of size N and integer K, the task is to split the array into K non-empty subarrays such that the sum of the difference between the maximum element and the minimum element of each subarray is minimized.
Note: Every element of the array must be included in one subarray and each subarray should be non-empty.
Examples:
Input: arr[] = {5, 9, 16, 17, 24, 43}, K = 3
Output: 12
Explanation: {5, 9}, {16, 17, 24}, {43} are the three subarrays because
(9-5) + (24-16) + (43-43) = 12 is minimum of all possible subarrays.Input: arr[] = [5, 7, 8, 8, 11, 14, 22}, K = 3
Output: 13
Explanation: {5, 7}, {8, 8}, {11, 14, 22}. So, (7 – 5) + (8 – 8) + (22 – 11) = 13
The given array of length 5 cannot be split into subsets of 4.
Approach: The problem can be solved based on the following idea:
We have to choose K-1 indexes from the array to form K subarrays.
If N is the length of the array and suppose we have chosen K-1 indices (i.e. a < b < . . . < c) then the required sum of K-subarrays will be
(arr[a] – arr[0]) + (arr[b] – arr[a+1]) + . . . + (arr – arr[b+1]) + (arr[N-1] – arr).On rearranging: (arr[N-1] – arr[0]) +(arr[a] – arr[a+1]) + (arr[b] – arr[b+1]) + . . . + (arr – arr)).
So, initially answer is sum = arr[N-1] – arr[0] and to minimize the answer add K – 1 minimum pairs to sum.
Follow the below steps to implement the idea:
- Create an array and store the difference between adjacent elements.
- Sort the difference array.
- Pick the first K elements from the array.
- Add these values to the difference between arr[N-1] and arr[0].
Below is the implementation of the above approach:
C++14
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find minimum sum of // difference between the maximum // and the minimum element of each subarray int minimumSum( int arr[], int n, int k) { // Calculate the difference // between the adjacent elements // and store it in diff array int diff[n - 1]; for ( int i = 0; i < n - 1; i++) diff[i] = (arr[i] - arr[i + 1]); sort(diff, diff + n - 1); int sum = arr[n - 1] - arr[0]; for ( int i = 0; i < k - 1; i++) sum += diff[i]; // Return the required sum return sum; } // Driver code int main() { int arr[] = { 5, 9, 16, 17, 24, 43 }; int N = sizeof (arr) / sizeof (arr[0]); int K = 3; // Function call cout << minimumSum(arr, N, K); return 0; } |
Java
// Java code to implement the approach import java.io.*; import java.util.*; class GFG { // Function to find minimum sum of // difference between the maximum // and the minimum element of each subarray static int minimumSum( int arr[], int n, int k) { // Calculate the difference // between the adjacent elements // and store it in diff array int [] diff = new int [n - 1 ]; for ( int i = 0 ; i < n - 1 ; i++) diff[i] = (arr[i] - arr[i + 1 ]); Arrays.sort(diff); int sum = arr[n - 1 ] - arr[ 0 ]; for ( int i = 0 ; i < k - 1 ; i++) sum += diff[i]; // Return the required sum return sum; } public static void main(String[] args) { int arr[] = { 5 , 9 , 16 , 17 , 24 , 43 }; int N = arr.length; int K = 3 ; // Function call System.out.print(minimumSum(arr, N, K)); } } // This code is contributed by lokeshmvs21. |
Python3
# Python3 code to implement the approach # Function to find minimum sum of # difference between the maximum # and the minimum element of each subarray def minimumSum(arr, n, k) : # Calculate the difference # between the adjacent elements # and store it in diff array diff = [ 0 ] * (n - 1 ) for i in range (n - 1 ): diff[i] = (arr[i] - arr[i + 1 ]) diff.sort() sum = arr[n - 1 ] - arr[ 0 ] for i in range (k - 1 ): sum + = diff[i] # Return the required sum return sum # Driver code if __name__ = = "__main__" : arr = [ 5 , 9 , 16 , 17 , 24 , 43 ] N = len (arr) K = 3 # Function call print (minimumSum(arr, N, K)) # This code is contributed by sanjoy_62. |
C#
// C# code to implement the approach using System; public class GFG { // Function to find minimum sum of // difference between the maximum // and the minimum element of each subarray static int minimumSum( int [] arr, int n, int k) { // Calculate the difference // between the adjacent elements // and store it in diff array int [] diff = new int [n - 1]; for ( int i = 0; i < n - 1; i++) diff[i] = (arr[i] - arr[i + 1]); Array.Sort(diff); int sum = arr[n - 1] - arr[0]; for ( int i = 0; i < k - 1; i++) sum += diff[i]; // Return the required sum return sum; } static public void Main() { int [] arr = { 5, 9, 16, 17, 24, 43 }; int N = arr.Length; int K = 3; // Function call Console.WriteLine(minimumSum(arr, N, K)); } } // This code is contributed by Rohit Pradhan |
Javascript
<script> // JavaScript code for the above approach // Function to find minimum sum of // difference between the maximum // and the minimum element of each subarray function minimumSum(arr, n, k) { // Calculate the difference // between the adjacent elements // and store it in diff array let diff = new Array(n - 1); for (let i = 0; i < n - 1; i++) diff[i] = (arr[i] - arr[i + 1]); diff.sort( function (a, b) { return a - b }) let sum = arr[n - 1] - arr[0]; for (let i = 0; i < k - 1; i++) sum += diff[i]; // Return the required sum return sum; } // Driver code let arr = [5, 9, 16, 17, 24, 43]; let N = arr.length; let K = 3; // Function call document.write(minimumSum(arr, N, K)); // This code is contributed by Potta Lokesh </script> |
12
Time Complexity: O(N * logN)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!