Given an array, arr[] of size N and an integer K, the task is to split the array into K subarrays minimizing the sum of absolute difference between adjacent elements of each subarray.
Examples:
Input: arr[] = {1, 3, -2, 5, -1}, K = 2
Output: 13
Explanation: Split the array into following 2 subarrays: {1, 3, -2} and {5, -1}.Input: arr[] = {2, 14, 26, 10, 5, 12}, K = 3
Output: 24
Explanation: Splitting array into following 3 subarrays: {2, 14}, {26}, {10, 5, 12}.
Approach: The given problem can be solved based on the following observations:
The idea is to slice the array arr[] at ith index which gives maximum absolute difference of adjacent elements. Subtract it from the result. Slicing at K – 1 places will give K subarrays with minimum sum of absolute difference of adjacent elements.
Follow the steps below to solve the problem:
- Initialize an array, say new_Arr[], and an integer variable, say ans, to store total absolute difference sum.
- Traverse the array .
- Store absolute difference of adjacent elements, say arr[i+1] and arr[i] in new_Arr[] array.
- Increment ans by absolute difference of arr[i] and arr[i + 1]
- Sort the new_Arr[] array in descending order.
- Traverse the array from i = 0 to i = K-1
- Decrement ans by new_Arr[i].
- Finally, print ans.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to split an array into K subarrays// with minimum sum of absolute difference// of adjacent elements in each of K subarraysvoid absoluteDifference(int arr[], int N, int K){ // Stores the absolute differences // of adjacent elements int new_Arr[N - 1]; // Stores the answer int ans = 0; // Stores absolute differences of // adjacent elements in new_Arr for (int i = 0; i < N - 1; i++) { new_Arr[i] = abs(arr[i] - arr[i + 1]); // Stores the sum of all absolute // differences of adjacent elements ans += new_Arr[i]; } // Sorting the new_Arr // in decreasing order sort(new_Arr, new_Arr + N - 1, greater<int>()); for (int i = 0; i < K - 1; i++) { // Removing K - 1 elements // with maximum sum ans -= new_Arr[i]; } // Prints the answer cout << ans << endl;}// Driver codeint main(){ // Given array arr[] int arr[] = { 1, 3, -2, 5, -1 }; // Given K int K = 2; // Size of array int N = sizeof(arr) / sizeof(arr[0]); // Function Call absoluteDifference(arr, N, K); return 0;} |
Java
// java program for the above approachimport java.util.*;import java.util.Arrays;class GFG{ public static void reverse(int[] array) { // Length of the array int n = array.length; // Swapping the first half elements with last half // elements for (int i = 0; i < n / 2; i++) { // Storing the first half elements temporarily int temp = array[i]; // Assigning the first half to the last half array[i] = array[n - i - 1]; // Assigning the last half to the first half array[n - i - 1] = temp; } } // Function to split an array into K subarrays // with minimum sum of absolute difference // of adjacent elements in each of K subarrays public static void absoluteDifference(int arr[], int N, int K) { // Stores the absolute differences // of adjacent elements int new_Arr[] = new int[N - 1]; // Stores the answer int ans = 0; // Stores absolute differences of // adjacent elements in new_Arr for (int i = 0; i < N - 1; i++) { new_Arr[i] = Math.abs(arr[i] - arr[i + 1]); // Stores the sum of all absolute // differences of adjacent elements ans += new_Arr[i]; } // Sorting the new_Arr // in decreasing order Arrays.sort(new_Arr); reverse(new_Arr); for (int i = 0; i < K - 1; i++) { // Removing K - 1 elements // with maximum sum ans -= new_Arr[i]; } // Prints the answer System.out.println(ans); } // Driver code public static void main (String[] args) { // Given array arr[] int arr[] = { 1, 3, -2, 5, -1 }; // Given K int K = 2; // Size of array int N = arr.length; // Function Call absoluteDifference(arr, N, K); }}// This code is contributed by AnkThon |
Python3
# Python3 program for the above approach# Function to split an array into K subarrays# with minimum sum of absolute difference# of adjacent elements in each of K subarraysdef absoluteDifference(arr, N, K): # Stores the absolute differences # of adjacent elements new_Arr = [0 for i in range(N - 1)] # Stores the answer ans = 0 # Stores absolute differences of # adjacent elements in new_Arr for i in range(N - 1): new_Arr[i] = abs(arr[i] - arr[i + 1]) # Stores the sum of all absolute # differences of adjacent elements ans += new_Arr[i] # Sorting the new_Arr # in decreasing order new_Arr = sorted(new_Arr)[::-1] for i in range(K - 1): # Removing K - 1 elements # with maximum sum ans -= new_Arr[i] # Prints the answer print (ans)# Driver codeif __name__ == '__main__': # Given array arr[] arr = [ 1, 3, -2, 5, -1 ] # Given K K = 2 # Size of array N = len(arr) # Function Call absoluteDifference(arr, N, K)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{ public static void reverse(int[] array) { // Length of the array int n = array.Length; // Swapping the first half elements with // last half elements for(int i = 0; i < n / 2; i++) { // Storing the first half elements // temporarily int temp = array[i]; // Assigning the first half to // the last half array[i] = array[n - i - 1]; // Assigning the last half to // the first half array[n - i - 1] = temp; } } // Function to split an array into K subarrays// with minimum sum of absolute difference// of adjacent elements in each of K subarrayspublic static void absoluteDifference(int[] arr, int N, int K){ // Stores the absolute differences // of adjacent elements int[] new_Arr = new int[N - 1]; // Stores the answer int ans = 0; // Stores absolute differences of // adjacent elements in new_Arr for(int i = 0; i < N - 1; i++) { new_Arr[i] = Math.Abs(arr[i] - arr[i + 1]); // Stores the sum of all absolute // differences of adjacent elements ans += new_Arr[i]; } // Sorting the new_Arr // in decreasing order Array.Sort(new_Arr); reverse(new_Arr); for(int i = 0; i < K - 1; i++) { // Removing K - 1 elements // with maximum sum ans -= new_Arr[i]; } // Prints the answer Console.WriteLine(ans);}// Driver Codepublic static void Main (){ // Given array arr[] int[] arr = { 1, 3, -2, 5, -1 }; // Given K int K = 2; // Size of array int N = arr.Length; // Function Call absoluteDifference(arr, N, K);}}// This code is contributed by susmitakundugoaldanga |
Javascript
<script>// Javascript program for the above approachfunction reverse(array) { // Length of the array let n = array.length; // Swapping the first half elements // with last half elements for(let i = 0; i < n / 2; i++) { // Storing the first half // elements temporarily let temp = array[i]; // Assigning the first half // to the last half array[i] = array[n - i - 1]; // Assigning the last half // to the first half array[n - i - 1] = temp; } } // Function to split an array into K subarrays// with minimum sum of absolute difference// of adjacent elements in each of K subarraysfunction absoluteDifference(arr, N, K){ // Stores the absolute differences // of adjacent elements let new_Arr = new Array(N - 1).fill(0); // Stores the answer let ans = 0; // Stores absolute differences of // adjacent elements in new_Arr for(let i = 0; i < N - 1; i++) { new_Arr[i] = Math.abs(arr[i] - arr[i + 1]); // Stores the sum of all absolute // differences of adjacent elements ans += new_Arr[i]; } // Sorting the new_Arr // in decreasing order new_Arr.sort(); reverse(new_Arr); for(let i = 0; i < K - 1; i++) { // Removing K - 1 elements // with maximum sum ans -= new_Arr[i]; } // Print the answer document.write(ans);}// Driver Code// Given array arr[]let arr = [ 1, 3, -2, 5, -1 ];// Given Klet K = 2;// Size of arraylet N = arr.length;// Function CallabsoluteDifference(arr, N, K);// This code is contributed by splevel62</script> |
Output:
13
Time Complexity: O(N * Log(N))
Auxiliary Space: O(N)
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!