|
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
#include <bits/stdc++.h>
using namespace std;
int minimumSum(int arr[], int n, int k)
{
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 sum;
}
int main()
{
int arr[] = { 5, 9, 16, 17, 24, 43 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 3;
cout << minimumSum(arr, N, K);
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class GFG {
static int minimumSum(int arr[], int n, int k)
{
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 sum;
}
public static void main(String[] args)
{
int arr[] = { 5, 9, 16, 17, 24, 43 };
int N = arr.length;
int K = 3;
System.out.print(minimumSum(arr, N, K));
}
}
|
Python3
def minimumSum(arr, n, k) :
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 sum
if __name__ == "__main__":
arr = [ 5, 9, 16, 17, 24, 43 ]
N = len(arr)
K = 3
print(minimumSum(arr, N, K))
|
C#
using System;
public class GFG {
static int minimumSum(int[] arr, int n, int k)
{
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 sum;
}
static public void Main()
{
int[] arr = { 5, 9, 16, 17, 24, 43 };
int N = arr.Length;
int K = 3;
Console.WriteLine(minimumSum(arr, N, K));
}
}
|
Javascript
<script>
function minimumSum(arr, n, k)
{
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 sum;
}
let arr = [5, 9, 16, 17, 24, 43];
let N = arr.length;
let K = 3;
document.write(minimumSum(arr, N, K));
</script>
|
Time Complexity: O(N * logN)
Auxiliary Space: O(N)
|
