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 subarrayint 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 codeint 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 approachimport 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 subarraydef 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 codeif __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 approachusing 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!