Problem title
Difficulty
Avg time to solve

Split Array Into Fibonacci Sequence
Moderate
15 mins
Minimum insertions.
Hard
45 mins
Maximum Nesting Depth Of Two Valid Parentheses Strings
Moderate
30 mins
Find Valid Matrix
Moderate
30 mins
Minimum Costs Of Subsets
Hard
15 mins
Toss Strange Coins
Easy
15 mins
Ninja's Contract
Hard
45 mins
Ninja And Divisible Array
Moderate
15 mins
Create Lexicographically Greatest Array
Hard
45 mins
Car Pooling
Moderate
30 mins

Minimum Costs Of Subsets

Difficulty: HARD
Contributed By
Avg. time to solve
15 min
Success Rate
85%

Problem Statement

You are given an array ARR of ‘N’ Integers and an integer. Your task is to divide this array into ‘K’ subsets satisfying the following constraints-

1. Each element in ARR belongs to exactly one subset.
2. All the elements in a subset are unique.
3. Each subset has a size of ‘N’/ ’K’

Your task is to find the minimum cost of constructing the ‘K’ subset.

Cost of the construction of subsets is calculated as the sum of the maximum - the minimum of a subset. If there is no way to divide ARR into K subsets satisfying the constraints, print -1.

It is guaranteed that ‘K’ is a divisor of ‘N’.

For example :

[1,2,3,1,2,5] k=2
[[1,2,3],[1,2,5]] is a valid subset division. All the elements in each subset are unique and the the cost of construction is (3 - 1) + (5 - 1) = 6  
Input Format :
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

The first line and the only line of each test case contain two single space-separated integers, ‘N’ and ‘K’.

The second line of each test case contains N space-separated integers representing the elements of the array ARR. 
Output Format :
For each test case print the minimum cost of construction.
Output for each test case is printed in a separate line.
Note :
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 5
1 <= N <= 12
1 <= K <= N
1<= ARR[i] <= 20    
K is a devisor of the N

Time Limit: 1 sec
Sample Input 1 :
2 
4 2
1 4 5 9
5 5
1 2 3 4 5
Sample Output 1 :
 7
 0
Explanation of Sample Input 1 :
For the first test case [[1,4], [5,9]] is the required distribution.
ANS = ( 4 - 1) + (9 - 5) = 7
[ [1, 5], [9, 4] ] is also the valid distribution but the cost of construction is not minimum. 
For the second test case each subset has exactly one element [ [1], [2], [3], [4], [5] ]
ANS = (1 - 1) + (2 - 2) + (3 - 3) + (4 - 4) + (5 - 5)
Sample Input 2 :
2
6 3 
3 3 3 1 11 4
4 2 
7 11 7 11 
Sample Output 2 :
11
8
Reset Code
Full screen
copy-code
Console