Given a sorted array arr[] of N integers and an integer K, the task is to split the array into K subarrays such that the sum of the difference of maximum and minimum element of each subarray is minimized.
Examples:
Input: arr[] = {1, 3, 3, 7}, K = 4
Output: 0
Explanation:
The given array can be split into 4 subarrays as {1}, {3}, {3}, and {7}.
The difference between minimum and maximum of each subarray is:
1. {1}, difference = 1 – 1 = 0
2. {3}, difference = 3 – 3 = 0
3. {3}, difference = 3 – 3 = 0
4. {7}, difference = 7 – 7 = 0
Therefore, the sum all the difference is 0 which is minimized.Input: arr[] = {4, 8, 15, 16, 23, 42}, K = 3
Output: 12
Explanation:
The given array can be split into 3 subarrays as {4, 8, 15, 16}, {23}, and {42}.
The difference between minimum and maximum of each subarray is:
1. {4, 8, 15, 16}, difference = 16 – 4 = 12
2. {23}, difference = 23 – 23 = 0
3. {42}, difference = 42 – 42 = 0
Therefore, the sum all the difference is 12 which is minimized.
Approach: To split the given array into K subarrays with the given conditions, the idea is to split at indexes(say i) where the difference between elements arr[i+1] and arr[i] is largest. Below are the steps to implement this approach:
- Store the difference between consecutive pairs of elements in the given array arr[] into another array(say temp[]).
- Sort the array temp[] in increasing order.
- Initialise the total difference(say diff) as the difference of the first and last element of the given array arr[].
- Add the first K – 1 values from the array temp[] to the above difference.
- The value stored in diff is the minimum sum of the difference of maximum and minimum element of the K subarray.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the subarrayint find(int a[], int n, int k){ vector<int> v; // Add the difference to vectors for (int i = 1; i < n; ++i) { v.push_back(a[i - 1] - a[i]); } // Sort vector to find minimum k sort(v.begin(), v.end()); // Initialize result int res = a[n - 1] - a[0]; // Adding first k-1 values for (int i = 0; i < k - 1; ++i) { res += v[i]; }// Return the minimized sum return res;}// Driver Codeint main(){// Given array arr[] int arr[] = { 4, 8, 15, 16, 23, 42 }; int N = sizeof(arr) / sizeof(int);// Given Kint K = 3;// Function Call cout << find(arr, N, K) << endl; return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the subarraystatic int find(int a[], int n, int k){ Vector<Integer> v = new Vector<Integer>(); // Add the difference to vectors for(int i = 1; i < n; ++i) { v.add(a[i - 1] - a[i]); } // Sort vector to find minimum k Collections.sort(v); // Initialize result int res = a[n - 1] - a[0]; // Adding first k-1 values for(int i = 0; i < k - 1; ++i) { res += v.get(i); } // Return the minimized sum return res;}// Driver Codepublic static void main(String[] args){ // Given array arr[] int arr[] = { 4, 8, 15, 16, 23, 42 }; int N = arr.length; // Given K int K = 3; // Function Call System.out.print(find(arr, N, K) + "\n");}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approach# Function to find the subarraydef find(a, n, k): v = [] # Add the difference to vectors for i in range(1, n): v.append(a[i - 1] - a[i]) # Sort vector to find minimum k v.sort() # Initialize result res = a[n - 1] - a[0] # Adding first k-1 values for i in range(k - 1): res += v[i] # Return the minimized sum return res # Driver codearr = [ 4, 8, 15, 16, 23, 42 ]# Length of arrayN = len(arr)K = 3# Function Callprint(find(arr, N, K))# This code is contributed by sanjoy_62 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to find the subarraystatic int find(int []a, int n, int k){ List<int> v = new List<int>(); // Add the difference to vectors for(int i = 1; i < n; ++i) { v.Add(a[i - 1] - a[i]); } // Sort vector to find minimum k v.Sort(); // Initialize result int res = a[n - 1] - a[0]; // Adding first k-1 values for(int i = 0; i < k - 1; ++i) { res += v[i]; } // Return the minimized sum return res;}// Driver Codepublic static void Main(String[] args){ // Given array []arr int []arr = { 4, 8, 15, 16, 23, 42 }; int N = arr.Length; // Given K int K = 3; // Function Call Console.Write(find(arr, N, K) + "\n");}}// This code is contributed by Amit Katiyar |
Javascript
<script>// javascript program for the above approach // Function to find the subarray function find(a , n , k) { var v = []; // Add the difference to vectors for (i = 1; i < n; ++i) { v.push(a[i - 1] - a[i]); } // Sort vector to find minimum k v.sort((a,b)=>a-b); // Initialize result var res = a[n - 1] - a[0]; // Adding first k-1 values for (i = 0; i < k - 1; ++i) { res += v[i]; } // Return the minimized sum return res; } // Driver Code // Given array arr var arr = [ 4, 8, 15, 16, 23, 42 ]; var N = arr.length; // Given K var K = 3; // Function Call document.write(find(arr, N, K) + "\n");// This code contributed by aashish1995</script> |
12
Time Complexity: O(N), where N is the number of elements in the array.
Auxiliary Space: O(N), where N is the number of elements in the array.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
