##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1681.html

# 1681. Minimum Incompatibility (Hard)

You are given an integer array nums and an integer k. You are asked to distribute this array into k subsets of equal size such that there are no two equal elements in the same subset.

A subset's incompatibility is the difference between the maximum and minimum elements in that array.

Return the minimum possible sum of incompatibilities of the k subsets after distributing the array optimally, or return -1 if it is not possible.

A subset is a group integers that appear in the array with no particular order.

Example 1:

Input: nums = [1,2,1,4], k = 2
Output: 4
Explanation: The optimal distribution of subsets is [1,2] and [1,4].
The incompatibility is (2-1) + (4-1) = 4.
Note that [1,1] and [2,4] would result in a smaller sum, but the first subset contains 2 equal elements.

Example 2:

Input: nums = [6,3,8,1,3,1,2,2], k = 4
Output: 6
Explanation: The optimal distribution of subsets is [1,2], [2,3], [6,8], and [1,3].
The incompatibility is (2-1) + (3-2) + (8-6) + (3-1) = 6.


Example 3:

Input: nums = [5,3,3,6,3,3], k = 3
Output: -1
Explanation: It is impossible to distribute nums into 3 subsets where no two elements are equal in the same subset.


Constraints:

• 1 <= k <= nums.length <= 16
• nums.length is divisible by k
• 1 <= nums[i] <= nums.length

Related Topics:
Backtracking, Greedy

### Preprocess

• Sort A in asending order
• Handle special cases where k = 1 and k = N.

### State Definition

Let dp[mask][pre] be the minimum incompatibility we can get with:

• mask: If the ith bit is 0, then ith number is used. Otherwise, ith number is available.
• pre: the index of the number selected in the previous choice.

### State Transition

We allocate the subsets one by one. For each subset, we allocate the numbers in ascending order.

We can use the number of 1 bits in mask, i.e. __builtin_popcount(mask), to know how many numbers are available.

If __builtin_popcount(mask) is not divisible by sz, then in the current choice we need to consider pre. To avoid duplicate numbers in the same subset, we must choose a number that is greater than A[pre]. Assume we chose A[p], then we added A[p] - A[pre] into the incompatibility.

          pre  p
v   v
A:       1 2 2 3 4 4 5 5 6
subset:  1 2   3

delta
incompa-   3 - 2 = 1
tibility


Transition formula:

dp[mask][pre] = min( dp[mask - (1 << p)][p] + A[p] - A[pre] | pre < p < N && A[p] > A[pre] && (mask & (1 << p)) != 0 )


If __builtin_popcount(mask) is divisible by sz, then we are allocating for a new subset. Now pre doesn’t matter. We just need to pick the first available number.

dp[mask][0] = ... = dp[mask][N - 1] = min( dp[mask - (1 << p)][p] | 0 < p < N && (mask & (1 << p)) != 0 )

// OJ: https://leetcode.com/problems/minimum-incompatibility/
// Time: O(2^N * N^2)
// Space: O(2^N * N)
// Ref: https://leetcode-cn.com/problems/minimum-incompatibility/solution/lao-tao-lu-zhuang-tai-ya-suo-dp-by-newha-j58b/
class Solution {
public:
int minimumIncompatibility(vector<int>& A, int k) {
int N = A.size(), M = 1 << N, sz = N / k;
if (k == 1) {
set<int> s(begin(A), end(A));
return s.size() == A.size() ? *s.rbegin() - *s.begin() : -1;
}
if (k == N) return 0;
sort(begin(A), end(A));
int dp[M][N];
memset(dp, 0x3f, sizeof(dp)); // infinity
memset(dp[0], 0, sizeof(dp[0]));
for (int pre = 0; pre < N; ++pre) {
for (int p = pre + 1; p < N; ++p) {
if ((mask & (1 << p)) && A[p] > A[pre]) {
}
}
}
} else {
for (int p = 0; p < N; ++p) {
}
for (int i = 1; i < N; ++i) dp[mask][i] = dp[mask][0];
}
}
return dp[M - 1][0] > 10000 ? -1 : dp[M - 1][0];
}
};

• class Solution {
public int minimumIncompatibility(int[] nums, int k) {
int length = nums.length;
int[] value = new int[1 << length];
Arrays.fill(value, -1);
int[] freq = new int[length + 1];
for (int i = 0; i < 1 << length; i++) {
if (Integer.bitCount(i) == length / k) {
for (int j = 0; j < length; j++) {
if ((i & (1 << j)) != 0)
freq[nums[j]]++;
}
boolean flag = true;
for (int j = 1; j <= length; j++) {
if (freq[j] > 1) {
flag = false;
break;
}
}
if (flag) {
int low = Integer.MAX_VALUE, high = Integer.MIN_VALUE;
for (int j = 1; j <= length; ++j) {
if (freq[j] > 0) {
low = Math.min(low, j);
high = Math.max(high, j);
}
}
value[i] = high - low;
}
for (int j = 0; j < length; ++j) {
if ((i & (1 << j)) != 0) {
--freq[nums[j]];
}
}
}
}
int[] dp = new int[1 << length];
Arrays.fill(dp, -1);
dp[0] = 0;
for (int i = 1; i < 1 << length; i++) {
if (Integer.bitCount(i) % (length / k) == 0) {
for (int j = i; j != 0; j = (j - 1) & i) {
if (value[j] != -1 && dp[i ^ j] != -1) {
if (dp[i] == -1)
dp[i] = dp[i ^ j] + value[j];
else
dp[i] = Math.min(dp[i], dp[i ^ j] + value[j]);
}
}
}
}
return dp[(1 << length) - 1];
}
}

• // OJ: https://leetcode.com/problems/minimum-incompatibility/
// Time: O(2^N * N^2)
// Space: O(2^N * N)
// Ref: https://leetcode-cn.com/problems/minimum-incompatibility/solution/lao-tao-lu-zhuang-tai-ya-suo-dp-by-newha-j58b/
class Solution {
public:
int minimumIncompatibility(vector<int>& A, int k) {
int N = A.size(), M = 1 << N, sz = N / k;
if (k == 1) {
set<int> s(begin(A), end(A));
return s.size() == A.size() ? *s.rbegin() - *s.begin() : -1;
}
if (k == N) return 0;
sort(begin(A), end(A));
int dp[M][N];
memset(dp, 0x3f, sizeof(dp)); // infinity
memset(dp[0], 0, sizeof(dp[0]));
for (int pre = 0; pre < N; ++pre) {
for (int p = pre + 1; p < N; ++p) {
if ((mask & (1 << p)) && A[p] > A[pre]) {
}
}
}
} else {
for (int p = 0; p < N; ++p) {
}
for (int i = 1; i < N; ++i) dp[mask][i] = dp[mask][0];
}
}
return dp[M - 1][0] > 10000 ? -1 : dp[M - 1][0];
}
};

• class Solution:
def minimumIncompatibility(self, nums: List[int], k: int) -> int:
@cache
if mask == (1 << n) - 1:
return 0
d = {v: i for i, v in enumerate(nums) if (mask >> i & 1) == 0}
ans = inf
if len(d) < m:
return ans
for vs in combinations(d.keys(), m):
for v in vs:
nxt |= 1 << d[v]
ans = min(ans, max(vs) - min(vs) + dfs(nxt))
return ans

n = len(nums)
m = n // k
ans = dfs(0)
dfs.cache_clear()
return ans if ans < inf else -1


• func minimumIncompatibility(nums []int, k int) int {
n := len(nums)
m := n / k
const inf = 1 << 30
f := make([]int, 1<<n)
g := make([]int, 1<<n)
for i := range g {
f[i] = inf
g[i] = -1
}
for i := 1; i < 1<<n; i++ {
if bits.OnesCount(uint(i)) != m {
continue
}
s := map[int]struct{}{}
mi, mx := 20, 0
for j, x := range nums {
if i>>j&1 == 1 {
if _, ok := s[x]; ok {
break
}
s[x] = struct{}{}
mi = min(mi, x)
mx = max(mx, x)
}
}
if len(s) == m {
g[i] = mx - mi
}
}
f[0] = 0
for i := 0; i < 1<<n; i++ {
if f[i] == inf {
continue
}
s := map[int]struct{}{}
for j, x := range nums {
if _, ok := s[x]; !ok && i>>j&1 == 0 {
s[x] = struct{}{}
}
}
if len(s) < m {
continue
}
for j := mask; j > 0; j = (j - 1) & mask {
if g[j] != -1 {
f[i|j] = min(f[i|j], f[i]+g[j])
}
}
}
if f[1<<n-1] == inf {
return -1
}
return f[1<<n-1]
}

func min(a, b int) int {
if a < b {
return a
}
return b
}

func max(a, b int) int {
if a > b {
return a
}
return b
}

• function minimumIncompatibility(nums: number[], k: number): number {
const n = nums.length;
const m = Math.floor(n / k);
const g: number[] = Array(1 << n).fill(-1);
for (let i = 1; i < 1 << n; ++i) {
if (bitCount(i) !== m) {
continue;
}
const s: Set<number> = new Set();
let [mi, mx] = [20, 0];
for (let j = 0; j < n; ++j) {
if ((i >> j) & 1) {
if (s.has(nums[j])) {
break;
}
mi = Math.min(mi, nums[j]);
mx = Math.max(mx, nums[j]);
}
}
if (s.size === m) {
g[i] = mx - mi;
}
}
const inf = 1e9;
const f: number[] = Array(1 << n).fill(inf);
f[0] = 0;
for (let i = 0; i < 1 << n; ++i) {
if (f[i] === inf) {
continue;
}
const s: Set<number> = new Set();
for (let j = 0; j < n; ++j) {
if (((i >> j) & 1) === 0 && !s.has(nums[j])) {
}
}
if (s.size < m) {
continue;
}
for (let j = mask; j; j = (j - 1) & mask) {
if (g[j] !== -1) {
f[i | j] = Math.min(f[i | j], f[i] + g[j]);
}
}
}
return f[(1 << n) - 1] === inf ? -1 : f[(1 << n) - 1];
}

function bitCount(i: number): number {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}


• public class Solution {
public int MinimumIncompatibility(int[] nums, int k) {
int n = nums.Length;
int m = n / k;
int[] g = new int[1 << n];
Array.Fill(g, -1);
for (int i = 1; i < 1 << n; ++i) {
if (bitCount(i) != m) {
continue;
}
HashSet<int> s = new();
int mi = 20, mx = 0;
for (int j = 0; j < n; ++j) {
if ((i >> j & 1) == 1) {
if (s.Contains(nums[j])) {
break;
}
mi = Math.Min(mi, nums[j]);
mx = Math.Max(mx, nums[j]);
}
}
if (s.Count == m) {
g[i] = mx - mi;
}
}
int[] f = new int[1 << n];
int inf = 1 << 30;
Array.Fill(f, inf);
f[0] = 0;
for (int i = 0; i < 1 << n; ++i) {
if (f[i] == inf) {
continue;
}
HashSet<int> s = new();
for (int j = 0; j < n; ++j) {
if ((i >> j & 1) == 0 && !s.Contains(nums[j])) {
}
}
if (s.Count < m) {
continue;
}
for (int j = mask; j > 0; j = (j - 1) & mask) {
if (g[j] != -1) {
f[i | j] = Math.Min(f[i | j], f[i] + g[j]);
}
}
}
return f[(1 << n) - 1] == inf ? -1 : f[(1 << n) - 1];
}

private int bitCount(int x) {
int cnt = 0;
while (x > 0) {
x &= x - 1;
++cnt;
}
return cnt;
}
}