Minimum Subsets with Distinct Elements in C

Minimum Subsets with Distinct Elements in C: A Comprehensive Tutorial

Given an array of integers, partition its elements into the minimum number of subsets so that no subset contains duplicates. At first glance, this looks like a combinatorial optimization problem—but there’s an elegant insight that collapses it into a single statistic: the maximum frequency of any element.

This tutorial explores the reasoning, three implementation approaches (naive O(n²), sort O(n log n), hash O(n)), and everything you need to write robust C code that solves it.

---

Conceptual Introduction & Fundamentals

What is the Problem?

Given an array arr[], distribute its elements into the fewest possible subsets, where each subset must contain distinct elements (no duplicates inside a subset).

Examples:

text

Input: arr = [1, 2, 3, 4] Output: 1 (all distinct → one subset) Input: arr = [1, 2, 3, 3] Output: 2 ({1,2,3} and {3})

Why This Problem Matters

• Pattern recognition: Reduces a seemingly complex problem to one statistic.
• Frequency counting: Foundation for many counting and partition problems.
• Combinatorial reasoning: Pigeonhole principle in action.
• Interview preparation: Common coding interview question.
• Real-world applications: Task scheduling, resource allocation, exam seating.

The Key Insight

Every subset can contain at most one copy of any value. If a value v appears f(v) times, we need at least f(v) subsets to place all its copies. The most frequent value determines the minimum:

text

answer = max over all values of frequency

Why the Answer is Sufficient

Suppose the maximum frequency is m for value x. Create m empty subsets. Distribute the elements round-robin (each value goes to a different subset each time it appears). Since every value appears at most m times, each value fits into distinct subsets, so no subset gets a duplicate.

Approaches Overview

Approach	Time	Space
Naive nested loops	O(n²)	O(1)
Sorting	O(n log n)	O(1) or O(n)
Hash map	O(n) average	O(n)

---

Syntax & Core Mechanics

Approach 1: Naive Nested Loops

For each element, count its occurrences by scanning the array.

c

#include <stdio.h> int minSubsetsNaive(const int arr[], int n) { if (n <= 0) return 0; int maxCount = 0; for (int i = 0; i < n; i++) { int count = 0; for (int j = 0; j < n; j++) { if (arr[i] == arr[j]) count++; } if (count > maxCount) maxCount = count; } return maxCount; } int main(void) { int arr[] = {40, 50, 30, 40, 50, 30, 30}; int n = sizeof(arr) / sizeof(arr[0]); printf("%d\n", minSubsetsNaive(arr, n)); return 0; }

Expected output:

text

3

Time: O(n²), Space: O(1)

Approach 2: Sort + Linear Scan

After sorting, equal elements are adjacent. Track the run length.

c

#include <stdio.h> #include <stdlib.h> #include <string.h> static int compareInts(const void *a, const void *b) { int x = *(const int *)a; int y = *(const int *)b; return (x > y) - (x < y); } int minSubsetsSorted(const int arr_in[], int n) { if (n <= 0) return 0; if (n == 1) return 1; int *arr = malloc((size_t)n * sizeof(int)); if (arr == NULL) return -1; memcpy(arr, arr_in, (size_t)n * sizeof(int)); qsort(arr, n, sizeof(int), compareInts); int maxCount = 1; int currCount = 1; for (int i = 1; i < n; i++) { if (arr[i] == arr[i - 1]) currCount++; else currCount = 1; if (currCount > maxCount) maxCount = currCount; } free(arr); return maxCount; } int main(void) { int arr[] = {40, 50, 30, 40, 50, 30, 30}; int n = sizeof(arr) / sizeof(arr[0]); printf("%d\n", minSubsetsSorted(arr, n)); return 0; }

Expected output:

text

3

Time: O(n log n), Space: O(n) for copy

Approach 3: Hash Map (Optimal)

Insert into a hash map (key = value, value = frequency). Return the maximum frequency.

c

#include <stdio.h> #include <stdlib.h> #define TABLE_SIZE 4096 typedef struct { int *keys; int *counts; int *occupied; int capacity; } FreqMap; static unsigned int hashFunc(int key, int cap) { return ((unsigned int)key) % (unsigned int)cap; } FreqMap *createMap(int cap) { FreqMap *m = malloc(sizeof(FreqMap)); if (m == NULL) return NULL; m->keys = malloc((size_t)cap * sizeof(int)); m->counts = calloc((size_t)cap, sizeof(int)); m->occupied = calloc((size_t)cap, sizeof(int)); if (m->keys == NULL || m->counts == NULL || m->occupied == NULL) { free(m->keys); free(m->counts); free(m->occupied); free(m); return NULL; } m->capacity = cap; return m; } void freeMap(FreqMap *m) { if (m) { free(m->keys); free(m->counts); free(m->occupied); free(m); } } void increment(FreqMap *m, int key) { unsigned int idx = hashFunc(key, m->capacity); int start = (int)idx; while (m->occupied[idx]) { if (m->keys[idx] == key) { m->counts[idx]++; return; } idx = (idx + 1) % (unsigned int)m->capacity; if ((int)idx == start) return; } m->keys[idx] = key; m->counts[idx] = 1; m->occupied[idx] = 1; } int minSubsetsHash(const int arr[], int n) { if (n <= 0) return 0; FreqMap *m = createMap(TABLE_SIZE); if (m == NULL) return -1; for (int i = 0; i < n; i++) increment(m, arr[i]); int maxCount = 0; for (int i = 0; i < m->capacity; i++) { if (m->occupied[i] && m->counts[i] > maxCount) { maxCount = m->counts[i]; } } freeMap(m); return maxCount; } int main(void) { int arr[] = {40, 50, 30, 40, 50, 30, 30}; int n = sizeof(arr) / sizeof(arr[0]); printf("%d\n", minSubsetsHash(arr, n)); return 0; }

Expected output:

text

3

Time: O(n) average, Space: O(n)

Round-Robin Distribution Proof

If the maximum frequency is m for value x:

1. Create m empty subsets.
2. For each distinct value v appearing f(v) ≤ m times, assign its f(v) copies to f(v) distinct subsets.
3. Each subset gets at most one copy of v.

This yields a valid partition with exactly m subsets, and no smaller count can work (pigeonhole).

---

Full Practical Code Example with Explanation

This program implements all three approaches and verifies they agree on multiple datasets.

c

/** * min_subsets.c * Minimum number of subsets with distinct elements. * Compares naive, sorted, and hash map approaches. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <time.h> #define MAX_LINE_LEN 100 #define TABLE_SIZE 262144 /* ============================================================ * FreqMap * ============================================================ */ typedef struct { int *keys; int *counts; int *occupied; int capacity; } FreqMap; static unsigned int hashFunc(int key, int cap) { return ((unsigned int)key) % (unsigned int)cap; } FreqMap *createMap(int cap) { FreqMap *m = malloc(sizeof(FreqMap)); if (m == NULL) return NULL; m->keys = malloc((size_t)cap * sizeof(int)); m->counts = calloc((size_t)cap, sizeof(int)); m->occupied = calloc((size_t)cap, sizeof(int)); if (m->keys == NULL || m->counts == NULL || m->occupied == NULL) { free(m->keys); free(m->counts); free(m->occupied); free(m); return NULL; } m->capacity = cap; return m; } void freeMap(FreqMap *m) { if (m) { free(m->keys); free(m->counts); free(m->occupied); free(m); } } void increment(FreqMap *m, int key) { unsigned int idx = hashFunc(key, m->capacity); int start = (int)idx; while (m->occupied[idx]) { if (m->keys[idx] == key) { m->counts[idx]++; return; } idx = (idx + 1) % (unsigned int)m->capacity; if ((int)idx == start) return; } m->keys[idx] = key; m->counts[idx] = 1; m->occupied[idx] = 1; } /* ============================================================ * Approaches * ============================================================ */ int minSubsetsNaive(const int arr[], int n) { if (n <= 0) return 0; int maxCount = 0; for (int i = 0; i < n; i++) { int cnt = 0; for (int j = 0; j < n; j++) if (arr[i] == arr[j]) cnt++; if (cnt > maxCount) maxCount = cnt; } return maxCount; } static int compareInts(const void *a, const void *b) { int x = *(const int *)a; int y = *(const int *)b; return (x > y) - (x < y); } int minSubsetsSorted(const int arr_in[], int n) { if (n <= 0) return 0; if (n == 1) return 1; int *arr = malloc((size_t)n * sizeof(int)); if (arr == NULL) return -1; memcpy(arr, arr_in, (size_t)n * sizeof(int)); qsort(arr, n, sizeof(int), compareInts); int maxCount = 1, currCount = 1; for (int i = 1; i < n; i++) { if (arr[i] == arr[i - 1]) currCount++; else currCount = 1; if (currCount > maxCount) maxCount = currCount; } free(arr); return maxCount; } int minSubsetsHash(const int arr[], int n) { if (n <= 0) return 0; FreqMap *m = createMap(TABLE_SIZE); if (m == NULL) return -1; for (int i = 0; i < n; i++) increment(m, arr[i]); int maxCount = 0; for (int i = 0; i < m->capacity; i++) { if (m->occupied[i] && m->counts[i] > maxCount) { maxCount = m->counts[i]; } } freeMap(m); return maxCount; } /* ============================================================ * Utility * ============================================================ */ void printArray(const int arr[], int n) { printf("["); for (int i = 0; i < n; i++) { printf("%d", arr[i]); if (i < n - 1) printf(", "); } printf("]"); } static void demoBasic(void) { printf("\n=== Sample Arrays ===\n"); int a1[] = {1, 2, 3, 4}; int a2[] = {1, 2, 3, 3}; int a3[] = {40, 50, 30, 40, 50, 30, 30}; int a4[] = {1, 2, 1, 2, 3, 3, 2, 2}; struct { int *arr; int n; const char *label; } tests[] = { {a1, 4, "[1,2,3,4]"}, {a2, 4, "[1,2,3,3]"}, {a3, 7, "[40,50,30,40,50,30,30]"}, {a4, 8, "[1,2,1,2,3,3,2,2]"} }; int nt = sizeof(tests) / sizeof(tests[0]); for (int t = 0; t < nt; t++) { printf("\nTest %d: %s\n", t + 1, tests[t].label); printf(" Array: "); printArray(tests[t].arr, tests[t].n); printf("\n"); int r1 = minSubsetsNaive(tests[t].arr, tests[t].n); int r2 = minSubsetsSorted(tests[t].arr, tests[t].n); int r3 = minSubsetsHash(tests[t].arr, tests[t].n); printf(" Naive: %d\n Sorted: %d\n Hash: %d\n", r1, r2, r3); printf(" Verify: %s\n", (r1 == r2 && r2 == r3) ? "PASS" : "FAIL"); } printf("\n"); } static void demoEdgeCases(void) { printf("\n=== Edge Cases ===\n"); /* Empty */ printf("Empty array: naive=%d, sorted=%d, hash=%d\n", minSubsetsNaive(NULL, 0), minSubsetsSorted(NULL, 0), minSubsetsHash(NULL, 0)); /* Single */ int a1[] = {7}; printf("Single element: %d / %d / %d\n", minSubsetsNaive(a1, 1), minSubsetsSorted(a1, 1), minSubsetsHash(a1, 1)); /* All distinct */ int a2[] = {1, 2, 3, 4, 5}; printf("All distinct: %d / %d / %d (expect 1)\n", minSubsetsNaive(a2, 5), minSubsetsSorted(a2, 5), minSubsetsHash(a2, 5)); /* All same */ int a3[] = {9, 9, 9, 9}; printf("All same: %d / %d / %d (expect 4)\n", minSubsetsNaive(a3, 4), minSubsetsSorted(a3, 4), minSubsetsHash(a3, 4)); /* One dominant value */ int a4[] = {1, 1, 1, 1, 2, 3}; printf("One dominant: %d / %d / %d (expect 4)\n", minSubsetsNaive(a4, 6), minSubsetsSorted(a4, 6), minSubsetsHash(a4, 6)); /* Negatives */ int a5[] = {-1, -1, -2, -2, -3}; printf("Negatives: %d / %d / %d (expect 2)\n", minSubsetsNaive(a5, 5), minSubsetsSorted(a5, 5), minSubsetsHash(a5, 5)); /* Two values alternating */ int a6[] = {5, 6, 5, 6, 5, 6}; printf("Alternating: %d / %d / %d (expect 3)\n", minSubsetsNaive(a6, 6), minSubsetsSorted(a6, 6), minSubsetsHash(a6, 6)); /* Zeros */ int a7[] = {0, 0, 0, 1, 1}; printf("Zeros: %d / %d / %d (expect 3)\n", minSubsetsNaive(a7, 5), minSubsetsSorted(a7, 5), minSubsetsHash(a7, 5)); } static void performanceTest(void) { printf("\n=== Performance Comparison ===\n"); /* Naive small */ int smallN = 3000; int *sa = malloc((size_t)smallN * sizeof(int)); if (sa == NULL) return; srand(42); for (int i = 0; i < smallN; i++) sa[i] = rand() % 500; clock_t start, end; double t; start = clock(); int r1 = minSubsetsNaive(sa, smallN); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Naive (n=%d): result=%d, time=%.3f ms\n", smallN, r1, t); start = clock(); int r2 = minSubsetsSorted(sa, smallN); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Sorted (n=%d): result=%d, time=%.3f ms\n", smallN, r2, t); start = clock(); int r3 = minSubsetsHash(sa, smallN); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Hash (n=%d): result=%d, time=%.3f ms\n", smallN, r3, t); printf("Verify: %s\n", (r1 == r2 && r2 == r3) ? "PASS" : "FAIL"); free(sa); /* Large hash */ int largeN = 5000000; int *la = malloc((size_t)largeN * sizeof(int)); if (la == NULL) return; for (int i = 0; i < largeN; i++) la[i] = rand() % 100000; start = clock(); int r4 = minSubsetsHash(la, largeN); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Hash (n=%d): result=%d, time=%.3f ms\n", largeN, r4, t); free(la); } static int readInteger(const char *prompt, int *outValue) { char buffer[MAX_LINE_LEN]; char *endPtr; long val; printf("%s", prompt); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) return -1; errno = 0; val = strtol(buffer, &endPtr, 10); if (endPtr == buffer || (*endPtr != '\n' && *endPtr != '\0')) return -1; if (errno == ERANGE || val < -2147483647 - 1 || val > 2147483647) return -1; *outValue = (int)val; return 0; } static void demoInteractive(void) { int n; if (readInteger("Enter array size (0-10000): ", &n) != 0 || n < 0 || n > 10000) { printf("Invalid size.\n"); return; } int *arr = NULL; if (n > 0) { arr = malloc((size_t)n * sizeof(int)); if (arr == NULL) return; for (int i = 0; i < n; i++) { char p[40]; snprintf(p, sizeof(p), " arr[%d]: ", i); if (readInteger(p, &arr[i]) != 0) { printf("Invalid value.\n"); free(arr); return; } } } printf("\nMinimum subsets: %d\n", minSubsetsHash(arr, n)); free(arr); } int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Minimum Subsets with Distinct Elements Demo ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Demonstrate All Approaches\n"); printf("2. Edge Cases\n"); printf("3. Performance Comparison\n"); printf("4. Interactive\n"); printf("5. Exit\n"); printf("Enter choice: "); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { fprintf(stderr, "Error reading choice.\n"); return EXIT_FAILURE; } choice = atoi(buffer); switch (choice) { case 1: demoBasic(); break; case 2: demoEdgeCases(); break; case 3: performanceTest(); break; case 4: demoInteractive(); break; case 5: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice.\n"); break; } } return EXIT_SUCCESS; }

Explanation of the Approaches

1. Naive: For each element, count its frequency with a nested loop; track the maximum. O(n²).
2. Sorted: Sort; scan runs of equal elements. O(n log n).
3. Hash: Increment frequency in a hash map; find the maximum. O(n) average.

Expected Output (sample run)

text

=== Sample Arrays === Test 1: [1,2,3,4] Array: [1, 2, 3, 4] Naive: 1 Sorted: 1 Hash: 1 Verify: PASS Test 2: [1,2,3,3] Array: [1, 2, 3, 3] Naive: 2 Sorted: 2 Hash: 2 Verify: PASS Test 3: [40,50,30,40,50,30,30] Array: [40, 50, 30, 40, 50, 30, 30] Naive: 3 Sorted: 3 Hash: 3 Verify: PASS Test 4: [1,2,1,2,3,3,2,2] Array: [1, 2, 1, 2, 3, 3, 2, 2] Naive: 4 Sorted: 4 Hash: 4 Verify: PASS === Edge Cases === Empty array: naive=0, sorted=0, hash=0 Single element: 1 / 1 / 1 All distinct: 1 / 1 / 1 (expect 1) All same: 4 / 4 / 4 (expect 4) One dominant: 4 / 4 / 4 (expect 4) Negatives: 2 / 2 / 2 (expect 2) Alternating: 3 / 3 / 3 (expect 3) Zeros: 3 / 3 / 3 (expect 3)

---

Common Pitfalls, Edge Cases & Memory Considerations

1. Confusing “Distinct” with “Unique Values”

Each subset must have distinct elements within itself; elements may repeat across subsets.

2. Empty Array

Return 0 (no subsets needed). Guard explicitly.

3. Single Element

Exactly 1 subset is required.

4. All Same Values

The answer equals n (each subset holds one copy).

5. All Distinct

The answer is 1 (one subset holds everything).

6. Large Frequencies

The count fits in int for arrays up to INT_MAX elements; use size_t for very large arrays.

7. Hash Table Sizing

Undersized table → probe failures.

Solution: Size ≥ 2× number of distinct values (or ≥ 2× n).

8. Negative Keys

Cast to unsigned int in the hash function.

9. Sorting Mutates Input

Copy before sorting if preservation needed.

10. Memory Considerations

• Naive: O(1) extra space.
• Sorted: O(n) for the copy.
• Hash: O(n) for the frequency map.
• Free all dynamic allocations.

---

Summary & Best Practices

The minimum-subsets problem is a beautiful case of “reduce complexity to one statistic.” The answer is simply the maximum frequency of any value in the array.

Key Takeaways

• Answer = maximum frequency of any element.
• All distinct → 1 subset.
• All same → n subsets.
• Naive: O(n²) — educational.
• Sorted: O(n log n) — memory-friendly.
• Hash: O(n) average — optimal.

Best Practices

1. Use the hash map for O(n) average.
2. Use sorting when memory is tight.
3. Track the maximum frequency during the scan.
4. Handle empty arrays (0) and single elements (1).
5. Size hash tables ≥ 2× distinct values.
6. Cast negative keys to unsigned int.
7. Copy inputs before sorting if preservation matters.
8. Free allocated memory.
9. Test edge cases: empty, single, all-same, all-distinct, negatives.
10. Profile for large inputs.

By mastering this problem, you’ll recognize reductions from combinatorial problems to single statistics—a powerful pattern across algorithms.