Split array into K subarrays with minimum sum of absolute difference between adjacent elements
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 subarrays void 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 code int 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 approach import 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 subarrays def 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 code if __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 approach using 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 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 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 Code public 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 approach function 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 subarrays function 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 K let K = 2; // Size of array let N = arr.length; // Function Call absoluteDifference(arr, N, K); // This code is contributed by splevel62 </script> |
13
Time Complexity: O(N * Log(N))
Auxiliary Space: O(N)
Contact Us