Given a sorted array of length ‘N’ and an integer ‘K'(K<N), the task is to remove exactly ‘K’ elements from the array such that the sum of the difference of consecutive elements of the array is minimized.
Examples:
Input : arr[] = {1, 2, 3, 4}, k = 1
Output : 2
Let's consider all possible cases.
a) Remove 0th index: arr[] = {2, 3, 4}, ans = 2
b) Remove 1th index: arr[] = {1, 3, 4}, ans = 3
c) Remove 2nd index: arr[] = {1, 2, 4}, ans = 3
d) Remove 3th index: arr[] = {1, 2, 3}, ans = 2
Minimum of them all is 2, thus answer = 2
Input : arr[] = {1, 2, 10}, k = 1
Output : 1
Approach :
Removing elements from the ends is the only possible way to decrease the value of the sum.
For instance, let the array = {1, 2, 3, 4}. If the second element in the array is removed, then the sum stays the same as the previous i.e. equal to 3. But, if the first or the last element is removed, the sum decreases to 2.
Greedy Approach: At each step, removing that element which decreases the sum by a greater amount. For example, let the array = {1, 3, 9, 33}, 33 is removed as it reduces the sum to 8 from 32.
But, this greedy approach won’t work for certain test-cases. Example. arr[] = {1, 2, 100, 120, 140} and k = 2. Here, the final array of greedy approach is {1, 2, 100} where as the optimal array is {100, 120, 140}.
Dynamic Programming: The states of the DP are as follows:
DP[l][r] means the minimum sum you can achieve by removing the required number of elements in the sub-array arr[l to r].
Thus, the recurrence relation will be
DP[l][r] = min(DP[l][r-1], DP[l+1][r])
Below is the C++ implementation of the above idea.
C++
// C++ implementation of the above approach.#include <bits/stdc++.h>using namespace std;#define N 100#define INF 1000000// states of DPint dp[N][N];bool vis[N][N];// function to find minimum sumint findSum(int* arr, int n, int k, int l, int r){ // base-case if ((l) + (n - 1 - r) == k) return arr[r] - arr[l]; // if state is solved before, return if (vis[l][r]) return dp[l][r]; // marking the state as solved vis[l][r] = 1; // recurrence relation return dp[l][r] = min(findSum(arr, n, k, l, r - 1), findSum(arr, n, k, l + 1, r));}// driver functionint32_t main(){ // input values int arr[] = { 1, 2, 100, 120, 140 }; int k = 2; int n = sizeof(arr) / sizeof(int); // callin the required function; cout << findSum(arr, n, k, 0, n - 1);} |
Java
// Java implementation of the above approach.class GFG{ final static int N = 100 ; final static int INF = 1000000 ; // states of DP static int dp[][] = new int[N][N]; static int vis[][] = new int[N][N]; // function to find minimum sum static int findSum(int []arr, int n, int k, int l, int r) { // base-case if ((l) + (n - 1 - r) == k) return arr[r] - arr[l]; // if state is solved before, return if (vis[l][r] == 1) return dp[l][r]; // marking the state as solved vis[l][r] = 1; // recurrence relation dp[l][r] = Math.min(findSum(arr, n, k, l, r - 1), findSum(arr, n, k, l + 1, r)); return dp[l][r] ; } // Driver function public static void main (String[] args) { // input values int arr[] = { 1, 2, 100, 120, 140 }; int k = 2; int n = arr.length; // calling the required function; System.out.println(findSum(arr, n, k, 0, n - 1)); } }// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the above approach. import numpy as npN = 100INF = 1000000# states of DP dp = np.zeros((N, N)); vis = np.zeros((N, N)); # function to find minimum sum def findSum(arr, n, k, l, r) : # base-case if ((l) + (n - 1 - r) == k) : return arr[r] - arr[l]; # if state is solved before, return if (vis[l][r]) : return dp[l][r]; # marking the state as solved vis[l][r] = 1; # recurrence relation dp[l][r] = min(findSum(arr, n, k, l, r - 1), findSum(arr, n, k, l + 1, r)); return dp[l][r]# driver function if __name__ == "__main__" : # input values arr = [ 1, 2, 100, 120, 140 ]; k = 2; n = len(arr); # calling the required function; print(findSum(arr, n, k, 0, n - 1)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the above approach.using System;class GFG{ static int N = 100 ; // states of DP static int [,]dp = new int[N, N]; static int [,]vis = new int[N, N]; // function to find minimum sum static int findSum(int []arr, int n, int k, int l, int r) { // base-case if ((l) + (n - 1 - r) == k) return arr[r] - arr[l]; // if state is solved before, return if (vis[l, r] == 1) return dp[l, r]; // marking the state as solved vis[l, r] = 1; // recurrence relation dp[l, r] = Math.Min(findSum(arr, n, k, l, r - 1), findSum(arr, n, k, l + 1, r)); return dp[l, r] ; } // Driver function public static void Main () { // input values int []arr = { 1, 2, 100, 120, 140 }; int k = 2; int n = arr.Length; // calling the required function; Console.WriteLine(findSum(arr, n, k, 0, n - 1)); } }// This code is contributed by AnkitRai01 |
Javascript
<script>// Javascript implementation of the above approach.var N = 100;var INF = 1000000;// states of DPvar dp = Array.from(Array(N), ()=> Array(N));var vis = Array.from(Array(N), ()=> Array(N));// function to find minimum sumfunction findSum(arr, n, k, l, r){ // base-case if ((l) + (n - 1 - r) == k) return arr[r] - arr[l]; // if state is solved before, return if (vis[l][r]) return dp[l][r]; // marking the state as solved vis[l][r] = 1; // recurrence relation dp[l][r] = Math.min(findSum(arr, n, k, l, r - 1), findSum(arr, n, k, l + 1, r)); return dp[l][r];}// driver function// input valuesvar arr = [1, 2, 100, 120, 140];var k= 2;var n = arr.length;// calling the required function;document.write( findSum(arr, n, k, 0, n - 1));</script> |
Output:
40
Time Complexity: O(n^2)
Space Complexity: O(n2) as 2d arrays like dp and vis has been created. Here n is size of the input array.
NOTE: An O(N) approach also exists for this problem. But the above-mentioned method can be used to solve the problem for unsorted arrays too with a little modification.
Alternate Approach:
Removing elements from left and right corner only. Therefore, if x elements are removed from the left, then K-x elements are removed from the right for every x in (0,K).
The sum of differences, if the above operation is performed, will be equal to arr[N-(K-X)-1] – arr[X].
On iterating the x from (0, K), the minimum value is picked among the obtained values.
Example:
Input: arr[] = {1, 3, 7, 8, 13} ; k = 3
Output: 1
Explanation:
Looping from X = 0 to X = K;
1) X = 0 and K-X = 3
So 0 elements removed from left and 3 from right.
array will be {1, 3} and answer will be 3 - 1 = 2.
min = 2
2) X = 1 and K-X = 2
So 1 elements removed from left and 2 from right.
array will be {3, 7} and answer will be 7 - 3 = 4.
min = 2
3) X = 2 and K-X = 1
So 2 elements removed from left and 1 from right.
array will be {7, 8} and answer will be 8 - 7 = 1.
min = 1
4) X = 3 and K-X = 0
So 3 elements removed from left and 0 from right.
array will be {8, 13} and answer will be 13 - 8 = 5.
min = 1
Below is the implementation of the above approach.
C++
//C++ implementation of the above approach.#include <bits/stdc++.h>using namespace std; // function to find minimum sumint findSum(int* arr, int n, int k){ // variable to store final answer // and initialising it with the values // when 0 elements is removed from the left and // K from the right. int ans = arr[n - k - 1] - arr[0]; // loop to simulate removal of elements for (int i = 1; i <= k; i++) { //removing i elements from the left and and K-i elements //from the right and updating the answer correspondingly ans = min(arr[n - 1 - (k - i)] - arr[i], ans); } // returning final answer return ans;} // driver functionint32_t main(){ // input values int arr[] = { 1, 2, 100, 120, 140 }; int k = 2; int n = sizeof(arr) / sizeof(int); // calling the required function; cout << findSum(arr, n, k);} |
Java
// Java implementation of the above approach. class GFG { // function to find minimum sum static int findSum(int []arr, int n, int k) { // variable to store final answer // and initialising it with the values // when 0 elements is removed from the left and // K from the right. int ans = arr[n - k - 1] - arr[0]; // loop to simulate removal of elements for (int i = 1; i <= k; i++) { // removing i elements from the left and and K-i elements // from the right and updating the answer correspondingly ans = Math.min(arr[n - 1 - (k - i)] - arr[i], ans); } // returning final answer return ans; } // Driver function public static void main (String[] args) { // input values int arr[] = { 1, 2, 100, 120, 140 }; int k = 2; int n = arr.length; // callin the required function; System.out.println(findSum(arr, n, k)); } }// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the above approach. # function to find minimum sum def findSum(arr, n, k) : # variable to store final answer # and initialising it with the values # when 0 elements is removed from the left and # K from the right. ans = arr[n - k - 1] - arr[0]; # loop to simulate removal of elements for i in range(1, k + 1) : # removing i elements from the left and and K-i elements # from the right and updating the answer correspondingly ans = min(arr[n - 1 - (k - i)] - arr[i], ans); # returning final answer return ans; # Driver codeif __name__ == "__main__" : # input values arr = [ 1, 2, 100, 120, 140 ]; k = 2; n = len(arr); # calling the required function; print(findSum(arr, n, k)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the above approach. using System;class GFG { // function to find minimum sum static int findSum(int []arr, int n, int k) { // variable to store final answer // and initialising it with the values // when 0 elements is removed from the left and // K from the right. int ans = arr[n - k - 1] - arr[0]; // loop to simulate removal of elements for (int i = 1; i <= k; i++) { // removing i elements from the left and and K-i elements // from the right and updating the answer correspondingly ans = Math.Min(arr[n - 1 - (k - i)] - arr[i], ans); } // returning final answer return ans; } // Driver function public static void Main () { // input values int []arr = { 1, 2, 100, 120, 140 }; int k = 2; int n = arr.Length; // calling the required function; Console.WriteLine(findSum(arr, n, k)); } } // This code is contributed by AnkitRai01 |
Javascript
<script>// Javascript implementation of the above approach. // function to find minimum sumfunction findSum(arr, n, k){ // variable to store final answer // and initialising it with the values // when 0 elements is removed from the left and // K from the right. var ans = arr[n - k - 1] - arr[0]; // loop to simulate removal of elements for (var i = 1; i <= k; i++) { // removing i elements from the left and and K-i elements // from the right and updating the answer correspondingly ans = Math.min(arr[n - 1 - (k - i)] - arr[i], ans); } // returning final answer return ans;} // driver function// input valuesvar arr = [1, 2, 100, 120, 140];var k = 2;var n = arr.length;// callin the required function;document.write( findSum(arr, n, k));// This code is contributed by noob2000.</script> |
Output:
40
Time Complexity: O(n), where n is the size of the given array
Auxiliary Space: O(1), as no extra space is required
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!
