Minimum incompatibility

Array Hash Table Dynamic Programming Bit Manipulation Bitmask

41.1% acceptance

Feb 25, 2026

298

101

You are given an integer array nums and an integer k. Distribute nums into k subsets of equal size such that there are no duplicate elements in the same subset. A subset's incompatibility is max - min. Return the minimum possible sum of incompatibilities, or -1 if not possible.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_incompatibility(nums: Vec<i32>, k: i32) -> i32 {
    let n = nums.len();
    let k = k as usize;
    let m = n / k; // group size

    // Each value can appear at most k times
    let mut count = [0usize; 17];
    for &x in &nums {
      count[x as usize] += 1;
      if count[x as usize] > k {
        return -1;
      }
    }

    // Precompute incompatibility for each mask of size m with all distinct elements
    const INF: i32 = i32::MAX / 2;
    let mut cost = vec![INF; 1 << n];
    for s in 0usize..(1 << n) {
      if s.count_ones() as usize != m {
        continue;
      }
      let mut vals: Vec<i32> =
        (0..n).filter(|&i| s >> i & 1 == 1).map(|i| nums[i]).collect();
      vals.sort_unstable();
      if (0..m - 1).all(|i| vals[i] != vals[i + 1]) {
        cost[s] = vals[m - 1] - vals[0];
      }
    }

    let full = (1usize << n) - 1;
    let mut dp = vec![INF; 1 << n];
    dp[0] = 0;

    for s in 1usize..=(full) {
      if s.count_ones() as usize % m != 0 {
        continue;
      }
      let low = s & s.wrapping_neg(); // lowest set bit
      let rest = s ^ low;
      // Enumerate subsets of rest with popcount = m-1
      let mut r = rest;
      loop {
        if r.count_ones() as usize == m - 1 {
          let t = low | r;
          if cost[t] < INF {
            let prev = s ^ t;
            if dp[prev] < INF {
              let cand = dp[prev] + cost[t];
              if cand < dp[s] {
                dp[s] = cand;
              }
            }
          }
        }
        if r == 0 {
          break;
        }
        r = (r - 1) & rest;
      }
    }

    if dp[full] == INF { -1 } else { dp[full] }
  }
}