Last Updated: 23 Aug, 2021
Minimum Difference Of Subarrays
Moderate
Asked in company
You are given an array 'ARR' that consists of ‘N’ numbers. Your task is to split the array into two non-empty subarrays such that the absolute difference between their sum is minimum.
For example,
If the given array is [6,7,1,8,5]. We can split the array into [6,7,1] and [8,5].
Hence the answer will be |14-13| = 1 which is minimum.
Input Format:
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains a single integer, 'N,’ denoting the number of elements in 'ARR'.
The second line of each test case has ‘N’ integers corresponding to the elements of 'ARR'.
Output Format:
For each test case, print a single integer corresponding to the minimum absolute difference possible.
Print the output of each test case in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10^6
-10^3 <= 'ARR'[i] <= 10^3
Time limit: 1 sec
Approaches
In this approach, we will first store the prefix sum of the given array 'ARR' into an array 'PREFIXSUM'. 'PREFIXSUM'[i] denotes the sum of all elements from index 0 to i.
Now, We will compute the sum of both the subarrays using the 'PREFIXSUM' array and compare the minimum absolute difference.
Algorithm:
- We will declare an array 'PREFIXSUM' to store the prefix sum of the given array.
- Set 'PREFIXSUM' as 'ARR'.
- For each index i from 1 to length of 'ARR'-1,do the following:
- Set 'PREFIXSUM'[i] as 'PREFIXSUM'[i] + 'PREFIXSUM'[i-1].
- Declare a variable 'MINDIFF' to store the absolute minimum difference.
- Declare a variable 'FIRSTSUM' to store the sum of the first subarray.
- Declare a variable 'LASTSUM' to store the sum of the last subarray.
- Set 'MINDIFF' as max_int.
- For index i in range 0 to length of 'ARR' - 2,do the following:
- Set 'FIRSTSUM' as 'PREFIXSUM'[i].(Sum of first subarray)
- Set 'LASTSUM' as 'PREFIXSUM'[length of 'ARR'-1]-'PREFIXSUM'[i]. (Sum of last subarray)
- Set minDiiff as minimum of 'MINDIFF' and absolute difference of 'FIRSTSUM' and 'LASTSUM'.
- Return 'MINDIFF'.
In this approach, we will first store the sum of all elements in an integer 'TOTALSUM'.We will declare a variable 'CURRENTSUM' to store the sum of the first subarray and the sum of the remaining array will be computed as 'TOTALSUM' - 'CURRENTSUM'. Now we will compare the minimum absolute difference for each index.
Algorithm:
- We will declare a variable 'TOTALSUM' to store the sum of all the elements of the given array 'ARR'.
- Set 'TOTALSUM' as 0.
- For each index idx from 0 to length of 'ARR'-1,do the following:
- Set 'TOTALSUM' as 'TOTALSUM' + 'ARR'[idx].
- Declare a variable 'CURRENTSUM' to store the sum of the first subarray.
- Set 'CURRENTSUM' as 0.
- Declare a variable named 'MINDIFF' to store the minimum absolute difference.
- For each index idx from 0 to length of 'ARR' -2, do the following:
- Set 'CURRENTSUM' as 'CURRENTSUM'+'ARR'[idx]
- Set 'MINDIFF' as the minimum of 'MINDIFF' and absolute difference of 'CURRENTSUM' and 'TOTALSUM'-'CURRENTSUM'.
- Return 'MINDIFF'.
Similar problems