Subarray whose absolute sum is closest to K
Given an array of n elements and an integer K, the task is to find the subarray with minimum value of ||a[i] + a[i + 1] + ……. a[j]| – K|. In other words, find the contiguous sub-array whose sum of elements shows minimum deviation from K or the subarray whose absolute sum is closest to K.
Example
Input:: a[] = {1, 3, 7, 10}, K = 15
Output: Subarray {7, 10}
The contiguous sub-array [7, 10] shows minimum deviation of 2 from 15.Input: a[] = {1, 2, 3, 4, 5, 6}, K = 6
Output: Subarray {1, 2, 3}
The contiguous sub-array [1, 2, 3] shows minimum deviation of 0 from 6.
A naive approach would be to check if the sum of each contiguous sub-array and its difference from K.
Below is the implementation of the above approach:
C++
// C++ code to find sub-array whose // sum shows the minimum deviation #include <bits/stdc++.h>using namespace std;int* getSubArray(int arr[], int n, int K) { int i = -1; int j = -1; int currSum = 0; // Starting index, ending index, // Deviation int* result = new int[3]{ i, j, abs(K - abs(currSum)) }; // Iterate i and j to get all subarrays for(i = 0; i < n; i++) { currSum = 0; for(j = i; j < n; j++) { currSum += arr[j]; int currDev = abs(K - abs(currSum)); // Found sub-array with less sum if (currDev < result[2]) { result[0] = i; result[1] = j; result[2] = currDev; } // Exactly same sum if (currDev == 0) return result; } } return result; } // Driver code int main(){ int arr[8] = { 15, -3, 5, 2, 7, 6, 34, -6 }; int n = sizeof(arr) / sizeof(arr[0]); int K = 50; // Array to store return values int* ans = getSubArray(arr, n, K); if (ans[0] == -1) { cout << "The empty array shows " << "minimum Deviation"; } else { for(int i = ans[0]; i <= ans[1]; i++) cout << arr[i] << " "; } return 0;}// This code is contributed by divyeshrabadiya07 |
Java
// Java code to find sub-array whose// sum shows the minimum deviationclass GFG{ public static int[] getSubArray(int[] arr, int n,int K){ int i = -1; int j = -1; int currSum = 0; // Starting index, ending index, Deviation int [] result = { i, j, Math.abs(K - Math.abs(currSum)) }; // Iterate i and j to get all subarrays for(i = 0; i < n; i++) { currSum = 0; for(j = i; j < n; j++) { currSum += arr[j]; int currDev = Math.abs(K - Math.abs(currSum)); // Found sub-array with less sum if(currDev < result[2]) { result[0] = i; result[1] = j; result[2] = currDev; } // Exactly same sum if(currDev == 0) return result; } } return result;}// Driver Code public static void main(String[] args){ int[] arr = { 15, -3, 5, 2, 7, 6, 34, -6 }; int n = arr.length; int K = 50; // Array to store return values int[] ans = getSubArray(arr, n, K); if(ans[0] == -1) { System.out.println("The empty array " + "shows minimum Deviation"); } else { for(int i = ans[0]; i <= ans[1]; i++) System.out.print(arr[i] + " "); }}}// This code is contributed by dadimadhav |
Python
# Python Code to find sub-array whose # sum shows the minimum deviationdef getSubArray(arr, n, K): i = -1 j = -1 currSum = 0 # starting index, ending index, Deviation result = [i, j, abs(K-abs(currSum))] # iterate i and j to get all subarrays for i in range(0, n): currSum = 0 for j in range(i, n): currSum += arr[j] currDev = abs(K-abs(currSum)) # found sub-array with less sum if (currDev < result[2]): result = [i, j, currDev] # exactly same sum if (currDev == 0): return result return result # Driver Codedef main(): arr = [15, -3, 5, 2, 7, 6, 34, -6] n = len(arr) K = 50 [i, j, minDev] = getSubArray(arr, n, K) if(i ==-1): print("The empty array shows minimum Deviation") return 0 for i in range(i, j + 1): print arr[i], main() |
C#
// C# code to find sub-array whose// sum shows the minimum deviationusing System;class GFG{ public static int[] getSubArray(int[] arr, int n, int K){ int i = -1; int j = -1; int currSum = 0; // Starting index, ending index, Deviation int [] result = { i, j, Math.Abs(K - Math.Abs(currSum)) }; // Iterate i and j to get all subarrays for(i = 0; i < n; i++) { currSum = 0; for(j = i; j < n; j++) { currSum += arr[j]; int currDev = Math.Abs(K - Math.Abs(currSum)); // Found sub-array with less sum if (currDev < result[2]) { result[0] = i; result[1] = j; result[2] = currDev; } // Exactly same sum if (currDev == 0) return result; } } return result;}// Driver Code public static void Main(string[] args){ int[] arr = { 15, -3, 5, 2, 7, 6, 34, -6 }; int n = arr.Length; int K = 50; // Array to store return values int[] ans = getSubArray(arr, n, K); if (ans[0] == -1) { Console.Write("The empty array " + "shows minimum Deviation"); } else { for(int i = ans[0]; i <= ans[1]; i++) Console.Write(arr[i] + " "); }}}// This code is contributed by rutvik_56 |
Javascript
<script>// Javascript code to find sub-array whose// sum shows the minimum deviationfunction getSubArray(arr, n, K){ let i = -1; let j = -1; let currSum = 0; // Starting index, ending index, Deviation let result = [ i, j, Math.abs(K - Math.abs(currSum)) ]; // Iterate i and j to get all subarrays for(i = 0; i < n; i++) { currSum = 0; for(j = i; j < n; j++) { currSum += arr[j]; let currDev = Math.abs(K - Math.abs(currSum)); // Found sub-array with less sum if(currDev < result[2]) { result[0] = i; result[1] = j; result[2] = currDev; } // Exactly same sum if(currDev == 0) return result; } } return result;}// driver code let arr = [ 15, -3, 5, 2, 7, 6, 34, -6 ]; let n = arr.length; let K = 50; // Array to store return values let ans = getSubArray(arr, n, K); if(ans[0] == -1) { document.write("The empty array " + "shows minimum Deviation"); } else { for(let i = ans[0]; i <= ans[1]; i++) document.write(arr[i] + " "); } </script> |
Output:
-3 5 2 7 6 34
Complexity Analysis:
- Time Complexity: O(N²)
- Auxiliary Space: O(1)
Efficient Approach:
If the array only consists of non-negative integers, use the sliding window technique to improve the calculation time for sum in each iteration. The sliding window technique reduces the complexity by calculating the new sub-array sum using the previous sub-array sum. Increase the right index till the difference (K-sum) is greater than zero. The first sub-array with negative (K-sum) is considered, and the next sub-array is with left index = i+1(where i is the current right index).
Below is the implementation of the above approach:
C++
// C++ code to find non-negative sub-array// whose sum shows minimum deviation. This// works only if all elements in array are// non-negative#include <bits/stdc++.h>using namespace std;struct Pair{ int f, s, t; Pair(int f, int s, int t) { this->f = f; this->s = s; this->t = t; }};// Function to return the index Pair* getSubArray(int *arr, int n, int K){ int currSum = 0; int prevDif = 0; int currDif = 0; Pair *result = new Pair( -1, -1, abs(K - abs(currSum))); Pair *resultTmp = result; int i = 0; int j = 0; while (i<= j && j<n) { // Add Last element tp currSum currSum += arr[j]; // Save Difference of previous Iteration prevDif = currDif; // Calculate new Difference currDif = K - abs(currSum); // When the Sum exceeds K if (currDif <= 0) { if (abs(currDif) < abs(prevDif)) { // Current Difference greater // in magnitude. Store Temporary // Result resultTmp = new Pair(i, j, currDif); } else { // Difference in Previous was lesser // In previous, Right index = j-1 resultTmp = new Pair(i, j - 1, prevDif); // In next iteration, Left Index Increases // but Right Index remains the Same // Update currSum and i Accordingly currSum -= (arr[i] + arr[j]); i += 1; } } // Case to simply increase Right Index else { resultTmp = new Pair(i, j, currDif); j += 1; } if (abs(resultTmp->t) < abs(result->t)) { // Check if lesser deviation found result = resultTmp; } } return result;}// Driver Codeint main(){ int arr[] = { 15, -3, 5, 2, 7, 6, 34, -6 }; int n = sizeof(arr) / sizeof(arr[0]); int K = 50; Pair *tmp = getSubArray(arr, n, K); int i = tmp->f; int j = tmp->s; int minDev = tmp->t; if (i == -1) { cout << "The empty array shows minimum Deviation" << endl; return 0; } for(int k = i + 1; k < j + 1; k++) { cout << arr[k] << " "; } return 0;}// This code is contributed by pratham76 |
Java
// Java code to find non-negative sub-array// whose sum shows minimum deviation. This// works only if all elements in array are// non-negativeimport java.util.*;class GFG{static class Pair{ int f, s, t; Pair(int f, int s, int t) { this.f = f; this.s = s; this.t = t; }};// Function to return the index static Pair getSubArray(int []arr, int n, int K){ int currSum = 0; int prevDif = 0; int currDif = 0; Pair result = new Pair( -1, -1, Math.abs(K - Math.abs(currSum))); Pair resultTmp = result; int i = 0; int j = 0; while (i<= j && j<n) { // Add Last element tp currSum currSum += arr[j]; // Save Difference of previous Iteration prevDif = currDif; // Calculate new Difference currDif = K - Math.abs(currSum); // When the Sum exceeds K if (currDif <= 0) { if (Math.abs(currDif) < Math.abs(prevDif)) { // Current Difference greater // in magnitude. Store Temporary // Result resultTmp = new Pair(i, j, currDif); } else { // Difference in Previous was lesser // In previous, Right index = j-1 resultTmp = new Pair(i, j - 1, prevDif); // In next iteration, Left Index Increases // but Right Index remains the Same // Update currSum and i Accordingly currSum -= (arr[i] + arr[j]); i += 1; } } // Case to simply increase Right Index else { resultTmp = new Pair(i, j, currDif); j += 1; } if (Math.abs(resultTmp.t) < Math.abs(result.t)) { // Check if lesser deviation found result = resultTmp; } } return result;}// Driver Codepublic static void main(String[] args){ int arr[] = { 15, -3, 5, 2, 7, 6, 34, -6 }; int n = arr.length; int K = 50; Pair tmp = getSubArray(arr, n, K); int i = tmp.f; int j = tmp.s; int minDev = tmp.t; if (i == -1) { System.out.print("The empty array shows minimum Deviation" +"\n"); return ; } for(int k = i + 1; k < j + 1; k++) { System.out.print(arr[k]+ " "); } }}// This code is contributed by 29AjayKumar |
Python
# Python Code to find non-negative # sub-array whose sum shows minimum deviation# This works only if all elements# in array are non-negative# function to return the index def getSubArray(arr, n, K): currSum = 0 prevDif = 0 currDif = 0 result = [-1, -1, abs(K-abs(currSum))] resultTmp = result i = 0 j = 0 while(i<= j and j<n): # Add Last element tp currSum currSum += arr[j] # Save Difference of previous Iteration prevDif = currDif # Calculate new Difference currDif = K - abs(currSum) # When the Sum exceeds K if(currDif <= 0): if abs(currDif) < abs(prevDif): # Current Difference greater in magnitude # Store Temporary Result resultTmp = [i, j, currDif] else: # Difference in Previous was lesser # In previous, Right index = j-1 resultTmp = [i, j-1, prevDif] # In next iteration, Left Index Increases # but Right Index remains the Same # Update currSum and i Accordingly currSum -= (arr[i]+arr[j]) i += 1 # Case to simply increase Right Index else: resultTmp = [i, j, currDif] j += 1 if(abs(resultTmp[2]) < abs(result[2])): # Check if lesser deviation found result = resultTmp return result# Driver Codedef main(): arr = [15, -3, 5, 2, 7, 6, 34, -6] n = len(arr) K = 50 [i, j, minDev] = getSubArray(arr, n, K) if(i ==-1): print("The empty array shows minimum Deviation") return 0 for i in range(i, j+1): print arr[i], main() |
C#
// C# code to find non-negative sub-array// whose sum shows minimum deviation. This// works only if all elements in array are// non-negativeusing System;public class GFG{ class Pair { public int f, s, t; public Pair(int f, int s, int t) { this.f = f; this.s = s; this.t = t; } }; // Function to return the index static Pair getSubArray(int []arr, int n, int K) { int currSum = 0; int prevDif = 0; int currDif = 0; Pair result = new Pair( -1, -1, Math.Abs(K - Math.Abs(currSum))); Pair resultTmp = result; int i = 0; int j = 0; while (i <= j && j < n) { // Add Last element tp currSum currSum += arr[j]; // Save Difference of previous Iteration prevDif = currDif; // Calculate new Difference currDif = K - Math.Abs(currSum); // When the Sum exceeds K if (currDif <= 0) { if (Math.Abs(currDif) < Math.Abs(prevDif)) { // Current Difference greater // in magnitude. Store Temporary // Result resultTmp = new Pair(i, j, currDif); } else { // Difference in Previous was lesser // In previous, Right index = j-1 resultTmp = new Pair(i, j - 1, prevDif); // In next iteration, Left Index Increases // but Right Index remains the Same // Update currSum and i Accordingly currSum -= (arr[i] + arr[j]); i += 1; } } // Case to simply increase Right Index else { resultTmp = new Pair(i, j, currDif); j += 1; } if (Math.Abs(resultTmp.t) < Math.Abs(result.t)) { // Check if lesser deviation found result = resultTmp; } } return result; } // Driver Code public static void Main(String[] args) { int []arr = { 15, -3, 5, 2, 7, 6, 34, -6 }; int n = arr.Length; int K = 50; Pair tmp = getSubArray(arr, n, K); int i = tmp.f; int j = tmp.s; int minDev = tmp.t; if (i == -1) { Console.Write("The empty array shows minimum Deviation" +"\n"); return ; } for(int k = i + 1; k < j + 1; k++) { Console.Write(arr[k]+ " "); } }}// This code is contributed by 29AjayKumar |
Javascript
// JavaScript code to find non-negative sub-array// whose sum shows minimum deviation. This// works only if all elements in array are// non-negativeclass Pair { constructor(f, s, t) { this.f = f; this.s = s; this.t = t; }}// Function to return the index function getSubArray(arr, n, K) { let currSum = 0; let prevDif = 0; let currDif = 0; let result = new Pair(-1, -1, Math.abs(K - Math.abs(currSum))); let resultTmp = result; let i = 0; let j = 0; while (i <= j && j < n) { // Add Last element to currSum currSum += arr[j]; // Save Difference of previous Iteration prevDif = currDif; // Calculate new Difference currDif = K - Math.abs(currSum); // When the Sum exceeds K if (currDif <= 0) { if (Math.abs(currDif) < Math.abs(prevDif)) { // Current Difference greater // in magnitude. Store Temporary // Result resultTmp = new Pair(i, j, currDif); } else { // Difference in Previous was lesser // In previous, Right index = j-1 resultTmp = new Pair(i, j - 1, prevDif); // In next iteration, Left Index Increases // but Right Index remains the Same // Update currSum and i Accordingly currSum -= (arr[i] + arr[j]); i += 1; } } // Case to simply increase Right Index else { resultTmp = new Pair(i, j, currDif); j += 1; } if (Math.abs(resultTmp.t) < Math.abs(result.t)) { // Check if lesser deviation found result = resultTmp; } } return result;}// Driver Codelet arr = [ 15, -3, 5, 2, 7, 6, 34, -6 ];let n = arr.length;let K = 50;let tmp = getSubArray(arr, n, K);let i = tmp.f;let j = tmp.s;let minDev = tmp.t;if (i == -1) { console.log("The empty array shows minimum Deviation");}for(let k = i + 1; k < j + 1; k++) { console.log(arr[k] + " ");}//Code is contributed by dhanshriborse |
Output
-3 5 2 7 6 34
Complexity Analysis:
- Time Complexity: O(N)
- Auxiliary Space: O(1)
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
