Minimum Difference Of Subarrays

Moderate
0/80
8 upvotes
Asked in company
Microsoft

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
5 
6 7 1 8 5
3
6 6 6
Sample Output 1:
1
6
Explanation of sample input 1:
For the first test case, 
We can split the array into [6,7] and [1,8,5]. The absolute difference is  |13-14| =1.
Hence,  the answer is 1.

For the second test case,
We can split the array into [6] and [6,6]. The absolute difference is |6-12| =6.
Hence, the answer is 6.
Sample Input 2:
2
5
4 1 20 9 9
4
7 9 8 10
Sample Output 2:
7
2
Hint

Can you store the sum of subarrays and check for the minimum difference?

Approaches (2)
Using Prefix Sum array

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'.
Time Complexity

O(N), where N is the number of elements in 'ARR'.

 

In this approach, we are traversing the array to compute the prefix sum and to compute the minimum absolute difference. Hence the overall time complexity is O(N).

Space Complexity

O(N), where N is the number of elements in 'ARR'.

 

We are using a 'PREFIXSUM' array to store the prefix sum of the given array. Hence the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Minimum Difference Of Subarrays
Full screen
Console