New update is available. Click here to update.

Last Updated: 12 Apr, 2021

Difficulty: Hard

```
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’
```

```
[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
```

```
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.
```

```
For each test case print the minimum cost of construction.
Output for each test case is printed in a separate line.
```

```
You don’t need to print anything. It has already been taken care of. Just implement the given function.
```

```
1 <= T <= 5
1 <= N <= 12
1 <= K <= N
1<= ARR[i] <= 20
K is a devisor of the N
Time Limit: 1 sec
```

The answer depends on the smallest and the largest element in the subset. We will iterate over all the submasks of the array and the last element taken in this mask. Number the set bits in the mask will give the idea about if we are starting a new subset or ending a current subset. We will create a subset from the smallest element to the largest element.

groupSize = size of each group/subset

If we are starting a new group with i’th element then this element will be the smallest element in our new group so we will subtract it

DP[new_mask][i] = min(dp[new_mask][i],DP[mask][last]-arr[i])

If we are ending a group with i’th element then this will be the largest element in our group so we will add it

DP[new_mask][i]=min(DP[new_mask][i],DP[mask][last]+arr[i])

If we are adding the i’th element and it is not starting or ending a group than

DP[new_mask][i]=min(DP[new_mask][i], DP[mask][last])

The algorithm will be :

- Calulate number of element in each subset (let groupSize= n/k)
- dp[(1<<n)][ n ]

dp[mask][last] represents the minimum cost to group all the elements in the mask and the last element taken is ‘last’

- For i in range(n)
- dp[1<<i][ i ] = - arr[i]

Base case here we are starting a new subset having only i’th element

- For mask in range((1<<n))
- SETBITS = number of set bits in mask
- For CURRENT in range(n)
- For NEXT in range(n)
- If CURRENT in mask and NEXT not in mask
- If SETBITS%groupSize == 0
- Start a new group

- If SETBITS%groupSize == groupSize - 1
- End the current group

- If 0 < SETBITS < groupSize - 1
- Add to current group

- For NEXT in range(n)

- ANS = infinity
- For i in range(n)
- ANS = min(ANS, dp[(1<<n) - 1][ i ] )

- If ANS == infinity
- ANS =- 1

- Return ANS

SIMILAR PROBLEMS

Equal Arrays

Posted: 29 Sep, 2022

Difficulty: Moderate

Randomly Sorted

Posted: 13 Nov, 2022

Difficulty: Moderate

Ninja And The Strictly Increasing Array

Posted: 27 Nov, 2022

Difficulty: Moderate

Maximize

Posted: 9 Dec, 2022

Difficulty: Easy

8-Queen Problem

Posted: 19 Dec, 2022

Difficulty: Easy

Popular Interview Problems: