Array partition with minimum difference

Hard
0/120
Average time to solve is 10m
371 upvotes
Asked in companies
Sterlite Technologies LimitedAccentureIntuit

Problem statement

You are given an array 'arr' containing 'n' non-negative integers.


Your task is to partition this array into two subsets such that the absolute difference between subset sums is minimum.


You just need to find the minimum absolute difference considering any valid division of the array elements.


Note:

1. Each array element should belong to exactly one of the subsets.

2. Subsets need not always be contiguous.
For example, for the array : [1, 2, 3], some of the possible divisions are 
   a) {1,2} and {3}
   b) {1,3} and {2}.

3. Subset-sum is the sum of all the elements in that subset.
Example: 
Input: 'n' = 5, 'arr' = [3, 1, 5, 2, 8].

Ouput: 1

Explanation: We can partition the given array into {3, 1, 5} and {2, 8}. 
This will give us the minimum possible absolute difference i.e. (10 - 9 = 1).
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains integer 'n' denoting the size of the array.

The second line of the input contains 'n' space-separated integers denoting the elements of the array 'arr'.
Output Format: 
Return the minimum possible absolute difference.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Sample Input 1:
4
1 2 3 4
Sample Output 1:
0
Explanation for sample input 1:
We can partition the given array into {2,3} and {1,4}.
This will give us the minimum possible absolute difference i.e. (5 - 5 = 0) in this case.
Sample Input 2:
3
8 6 5
Sample Output 2:
3
Explanation for sample input 2:
We can partition the given array into {8} and {6,5}. 
This will give us the minimum possible absolute difference i.e. (11 - 8 = 3).
Expected time complexity:
The expected time complexity is O(n * 𝚺 'arr'[i]), where 𝚺 'arr'[i] denotes the sum of all elements in 'arr'.
Constraints:
1 <= 'n' <= 10^3
0 <= 'arr'[i] <= 10^3
0 <= 𝚺 'arr'[i] <= 10^4, 

where 𝚺 'arr'[i] denotes the sum of all elements in 'arr'.

Time Limit: 1sec
Hint

Try all possible combinations.

Approaches (2)
Recursion
  • This problem can be solved using recursion. And the idea behind this is to generate all the possible sums from the given set.
  • We will try different combinations for one of the subsets and accordingly calculate the sums of both the subsets and store the minimum. Assume that the sum of elements of the array is ‘sum', and the sum of the elements of the first subset is ‘s1’. Thus, we can find the sum of the 2nd subset as ‘sum’ - ‘s1’.
  • For each element, we will have two choices: either to include it in the first subset or not. So, at each stage, we will make two recursive calls, one which will consider including the current element and the other which won’t. We will explore the depth considering each of the two possible cases.
  • When we have no elements to explore, we will consider  (abs(('sum' - ‘pathSum’) - ‘pathSum’) as one of the possible answers, where ‘pathSum’ is the subset sum achieved in the current recursive call. And finally, we will be taking the minimum of all such values to get the desired answer.
Time Complexity

O(2^n), where ‘n’ is the number of elements in the array.

 

Since here, to generate sums, we either include the ith item in set 1 or don’t include, i.e., include in set 2. So time complexity will be 2*2*..... *2 (For N times), that is O(2^n). 

 

Hence the overall time complexity is O(2^n).

Space Complexity

O(n), where ‘n’ is the number of elements in the array. 

 

The space complexity is O(n) because, in the case of recursion, the space complexity is proportional to the depth of the recursion tree, which in this case is proportional to the number of elements in the array.

 

Hence the overall space complexity is O(n).

Code Solution
(100% EXP penalty)
Array partition with minimum difference
Full screen
Console