Minimum Incompatibility - Practice Coding Problems

Minimum Incompatibility - Problem

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 of integers that appear in the array with no particular order.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,1,4], k = 2

› Output: 4

💡 Note: Optimal distribution: [1,4] and [1,2]. Incompatibilities: (4-1) + (2-1) = 3 + 1 = 4

Example 2 — Impossible Case

$ Input: nums = [6,3,8,1,3,1,2,2], k = 4

› Output: 6

💡 Note: Each subset has size 2. Possible distribution: [1,2], [1,3], [3,6], [2,8] with incompatibilities 1+2+3+6=12, but optimal is different

Example 3 — All Same Elements

$ Input: nums = [5,5,5,5], k = 2

› Output: -1

💡 Note: Cannot form 2 subsets without duplicate elements since all elements are the same

Constraints

1 ≤ k ≤ nums.length ≤ 16
nums.length is divisible by k
1 ≤ nums[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,2,1,4] with k=2 subsets needed

Distribute

Form 2 subsets of size 2 without duplicates within each

Calculate

Sum incompatibilities: (4-1) + (2-1) = 4

Key Takeaway

🎯 Key Insight: Use bitmask DP to efficiently explore all valid subset combinations while avoiding duplicate calculations

Asked in

G Google 15 f Facebook 8

The key insight is to use bitmask dynamic programming to efficiently track which elements have been used while avoiding redundant calculations. The optimal approach precomputes all valid subsets and uses DP to find minimum incompatibility sum. Time: O(3^n), Space: O(2^n)

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming with Bitmask	O(3^n)	O(2^n)	Use bitmask DP to avoid recalculating the same subset states
Brute Force Backtracking	O(k! × (n/k)^k)	O(n)	Try all possible ways to distribute elements into k subsets

Dynamic Programming with Bitmask — Algorithm Steps

Precompute all valid subsets of size n/k and their incompatibilities
Use bitmask to represent which elements are used
Apply DP: dp[mask] = minimum incompatibility sum using elements in mask
Try all valid subsets that don't overlap with current mask

Visualization

Tap to expand

Step-by-Step Walkthrough

Precompute

Calculate incompatibility for all valid subsets

Bitmask DP

Use mask to represent which elements are used

Combine

Try adding each valid subset to current state

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int popCount(int n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

int findMin(int* arr, int size) {
    int min = arr[0];
    for (int i = 1; i < size; i++) {
        if (arr[i] < min) min = arr[i];
    }
    return min;
}

int findMax(int* arr, int size) {
    int max = arr[0];
    for (int i = 1; i < size; i++) {
        if (arr[i] > max) max = arr[i];
    }
    return max;
}

int hasDuplicates(int* arr, int size) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = i + 1; j < size; j++) {
            if (arr[i] == arr[j]) return 1;
        }
    }
    return 0;
}

int solution(int* nums, int numsSize, int k) {
    int n = numsSize;
    if (n % k != 0) return -1;
    
    int subsetSize = n / k;
    
    // Check if distribution is possible
    int count[2001] = {0}; // Assuming nums[i] in range [-1000, 1000]
    for (int i = 0; i < n; i++) {
        count[nums[i] + 1000]++;
    }
    for (int i = 0; i < 2001; i++) {
        if (count[i] > k) return -1;
    }
    
    // For simplicity, limit to small n due to memory constraints
    if (n > 16) return -1;
    
    // Precompute incompatibilities for all valid subsets
    int* incomp = (int*)malloc((1 << n) * sizeof(int));
    for (int i = 0; i < (1 << n); i++) {
        incomp[i] = -1;
    }
    
    for (int mask = 0; mask < (1 << n); mask++) {
        if (popCount(mask) == subsetSize) {
            int subset[20];
            int subsetCount = 0;
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    subset[subsetCount++] = nums[i];
                }
            }
            // Check if subset has duplicates
            if (!hasDuplicates(subset, subsetCount)) {
                incomp[mask] = findMax(subset, subsetCount) - findMin(subset, subsetCount);
            }
        }
    }
    
    // DP with bitmask
    int* dp = (int*)malloc((1 << n) * sizeof(int));
    for (int i = 0; i < (1 << n); i++) {
        dp[i] = -1;
    }
    dp[0] = 0;
    
    for (int mask = 0; mask < (1 << n); mask++) {
        if (dp[mask] == -1) continue;
        
        // Try all valid subsets that don't overlap with current mask
        for (int subsetMask = 0; subsetMask < (1 << n); subsetMask++) {
            if (incomp[subsetMask] != -1 && (mask & subsetMask) == 0) {
                int newMask = mask | subsetMask;
                if (dp[newMask] == -1) {
                    dp[newMask] = dp[mask] + incomp[subsetMask];
                } else if (dp[mask] + incomp[subsetMask] < dp[newMask]) {
                    dp[newMask] = dp[mask] + incomp[subsetMask];
                }
            }
        }
    }
    
    int result = dp[(1 << n) - 1];
    
    free(incomp);
    free(dp);
    
    return result != -1 ? result : -1;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Parse array
    int nums[20];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(3^n)

For each mask, we iterate through all its subsets, giving 3^n total operations

✓ Linear Growth

Space Complexity

O(2^n)

DP array of size 2^n to store results for each possible bitmask

⚠ Quadratic Space

12.0K Views

Medium Frequency

~45 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming with Bitmask — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler