Missing Elements of a Range in an Array: C Guide
Missing Elements of a Range in an Array in C: A Comprehensive Tutorial
Given an array, let min and max be the smallest and largest elements. The task is to count how many integers must be added so that every value in [min, max] appears at least once. This problem is about counting gaps in a value range, not the indices of the array. It’s a compact exercise in reasoning about sets versus ranges.
This tutorial covers two approaches in C: sorting-based O(n log n) and hash-set-based O(n), each with portable C99/C11 code and complete output examples.
Conceptual Introduction & Fundamentals
What is the Problem?
Given arr[] of size n, let:
min= minimum elementmax= maximum elementrange_size = max - min + 1
Count how many integers in [min, max] are not present in the array.
Examples:
text
Input: [4, 5, 3, 8, 6] Output: 1 Explanation: Range is [3, 8]; only 7 is missing. Input: [2, 1, 3] Output: 0 Explanation: Range is [1, 3]; nothing is missing.
Why This Problem Matters
- Set vs range: Distinguishes distinct elements from the covered range.
- Handling duplicates: Sets collapse duplicates; arrays do not.
- Two clean solutions: Sorting and hashing with the same asymptotic idea.
- Real-world use: Completeness of ID ranges, sensor calibration ranges, exam number gaps.
- Interview preparation: Common coding interview question.
Key Identity
text
missing_count = (max - min + 1) - distinct_count
Where distinct_count is the number of unique values in the array.
Approaches Overview
| Approach | Time | Space |
|---|---|---|
| Sorting | O(n log n) | O(1) or O(n) |
| Hash set | O(n) average | O(n) |
Syntax & Core Mechanics
Approach 1: Sorting
Sort the array; walk adjacent pairs, adding gaps between distinct consecutive values.
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); } long long countMissingSorted(const int arr_in[], int n) { if (n <= 1) return 0; 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); long long missing = 0; for (int i = 0; i < n - 1; i++) { int cur = arr[i]; int nxt = arr[i + 1]; if (nxt > cur + 1) { missing += (long long)(nxt - cur - 1); } /* If nxt == cur (duplicate) or nxt == cur+1, add nothing. */ } free(arr); return missing; } int main(void) { int arr[] = {4, 5, 3, 8, 6}; int n = sizeof(arr) / sizeof(arr[0]); printf("%lld\n", countMissingSorted(arr, n)); return 0; } Expected output:
text
1
Time: O(n log n), Space: O(n) for copy
Why skip duplicates? Adjacent equal values contribute 0 to the gap because nxt - cur - 1 = -1, which would be wrong. The condition nxt > cur + 1 correctly skips both duplicates and consecutive integers.
Approach 2: Hash Set
Track distinct values in a set; also track min and max.
c
#include <stdio.h> #include <stdlib.h> #include <limits.h> #define TABLE_SIZE 8192 typedef struct { int *keys; int *occupied; int capacity; int size; } HashSet; static unsigned int hashFunc(int key, int cap) { return ((unsigned int)key) % (unsigned int)cap; } HashSet *createSet(int cap) { HashSet *s = malloc(sizeof(HashSet)); if (s == NULL) return NULL; s->keys = malloc((size_t)cap * sizeof(int)); s->occupied = calloc((size_t)cap, sizeof(int)); if (s->keys == NULL || s->occupied == NULL) { free(s->keys); free(s->occupied); free(s); return NULL; } s->capacity = cap; s->size = 0; return s; } void freeSet(HashSet *s) { if (s) { free(s->keys); free(s->occupied); free(s); } } int setInsert(HashSet *s, int key) { unsigned int idx = hashFunc(key, s->capacity); int start = (int)idx; while (s->occupied[idx]) { if (s->keys[idx] == key) return 0; /* Already present */ idx = (idx + 1) % (unsigned int)s->capacity; if ((int)idx == start) return -1; /* Full */ } s->keys[idx] = key; s->occupied[idx] = 1; s->size++; return 1; } long long countMissingHash(const int arr[], int n) { if (n <= 1) return 0; HashSet *s = createSet(TABLE_SIZE); if (s == NULL) return -1; int minv = INT_MAX, maxv = INT_MIN; for (int i = 0; i < n; i++) { setInsert(s, arr[i]); if (arr[i] < minv) minv = arr[i]; if (arr[i] > maxv) maxv = arr[i]; } long long range_size = (long long)maxv - (long long)minv + 1; long long result = range_size - (long long)s->size; freeSet(s); return result; } int main(void) { int arr[] = {4, 5, 3, 8, 6}; int n = sizeof(arr) / sizeof(arr[0]); printf("%lld\n", countMissingHash(arr, n)); return 0; } Expected output:
text
1
Time: O(n) average, Space: O(n)
Why Hash Wins for Large Inputs
The set approach handles unsorted input, duplicates, and arbitrarily wide ranges without allocating per-range memory.
Full Practical Code Example with Explanation
This program implements both approaches and verifies their agreement.
c
/** * missing_range_count.c * Counts how many integers are missing from [min, max] of an array. * Compares sorting and hash set approaches. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <limits.h> #include <time.h> #define MAX_LINE_LEN 100 #define TABLE_SIZE 262144 /* ============================================================ * HashSet * ============================================================ */ typedef struct { int *keys; int *occupied; int capacity; int size; } HashSet; static unsigned int hashFunc(int key, int cap) { return ((unsigned int)key) % (unsigned int)cap; } HashSet *createSet(int cap) { HashSet *s = malloc(sizeof(HashSet)); if (s == NULL) return NULL; s->keys = malloc((size_t)cap * sizeof(int)); s->occupied = calloc((size_t)cap, sizeof(int)); if (s->keys == NULL || s->occupied == NULL) { free(s->keys); free(s->occupied); free(s); return NULL; } s->capacity = cap; s->size = 0; return s; } void freeSet(HashSet *s) { if (s) { free(s->keys); free(s->occupied); free(s); } } int setInsert(HashSet *s, int key) { unsigned int idx = hashFunc(key, s->capacity); int start = (int)idx; while (s->occupied[idx]) { if (s->keys[idx] == key) return 0; idx = (idx + 1) % (unsigned int)s->capacity; if ((int)idx == start) return -1; } s->keys[idx] = key; s->occupied[idx] = 1; s->size++; return 1; } /* ============================================================ * Approaches * ============================================================ */ static int compareInts(const void *a, const void *b) { int x = *(const int *)a; int y = *(const int *)b; return (x > y) - (x < y); } long long countMissingSorted(const int arr_in[], int n) { if (n <= 1) return 0; 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); long long missing = 0; for (int i = 0; i < n - 1; i++) { int cur = arr[i], nxt = arr[i + 1]; if (nxt > cur + 1) { missing += (long long)(nxt - cur - 1); } } free(arr); return missing; } long long countMissingHash(const int arr[], int n) { if (n <= 1) return 0; HashSet *s = createSet(TABLE_SIZE); if (s == NULL) return -1; int minv = INT_MAX, maxv = INT_MIN; for (int i = 0; i < n; i++) { setInsert(s, arr[i]); if (arr[i] < minv) minv = arr[i]; if (arr[i] > maxv) maxv = arr[i]; } long long range_size = (long long)maxv - (long long)minv + 1; long long result = range_size - (long long)s->size; freeSet(s); return result; } /* ============================================================ * 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[] = {4, 5, 3, 8, 6}; int a2[] = {2, 1, 3}; int a3[] = {3, 5, 8, 6}; int a4[] = {10, 10, 10}; int a5[] = {1, 5, 10}; int a6[] = {-5, -2, 0, 1}; struct { int *arr; int n; const char *label; } tests[] = { {a1, 5, "[4,5,3,8,6]"}, {a2, 3, "[2,1,3]"}, {a3, 4, "[3,5,8,6]"}, {a4, 3, "[10,10,10]"}, {a5, 3, "[1,5,10]"}, {a6, 4, "[-5,-2,0,1]"} }; 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"); long long r1 = countMissingSorted(tests[t].arr, tests[t].n); long long r2 = countMissingHash(tests[t].arr, tests[t].n); printf(" Sorted: %lld\n Hash: %lld\n", r1, r2); printf(" Verify: %s\n", (r1 == r2) ? "PASS" : "FAIL"); } printf("\n"); } static void demoEdgeCases(void) { printf("\n=== Edge Cases ===\n"); /* Empty and single */ printf("Empty array: sorted=%lld, hash=%lld\n", countMissingSorted(NULL, 0), countMissingHash(NULL, 0)); int a1[] = {7}; printf("Single element: sorted=%lld, hash=%lld\n", countMissingSorted(a1, 1), countMissingHash(a1, 1)); /* All same */ int a2[] = {5, 5, 5, 5}; printf("[5,5,5,5]: sorted=%lld, hash=%lld (expect 0)\n", countMissingSorted(a2, 4), countMissingHash(a2, 4)); /* All consecutive */ int a3[] = {1, 2, 3, 4, 5}; printf("[1..5]: sorted=%lld, hash=%lld (expect 0)\n", countMissingSorted(a3, 5), countMissingHash(a3, 5)); /* Big gap */ int a4[] = {1, 1000000000}; printf("[1, 1e9]: sorted=%lld, hash=%lld (expect 999999998)\n", countMissingSorted(a4, 2), countMissingHash(a4, 2)); /* Duplicates + gaps */ int a5[] = {1, 1, 3, 5, 5, 5, 7}; printf("[1,1,3,5,5,5,7]: sorted=%lld, hash=%lld (expect 2: 2,4,6)\n", countMissingSorted(a5, 7), countMissingHash(a5, 7)); /* Negatives */ int a6[] = {-10, -8, -8, -5}; printf("[-10,-8,-8,-5]: sorted=%lld, hash=%lld (expect 3)\n", countMissingSorted(a6, 4), countMissingHash(a6, 4)); } static void performanceTest(void) { printf("\n=== Performance Comparison ===\n"); int n = 500000; int *arr = malloc((size_t)n * sizeof(int)); if (arr == NULL) return; srand(42); for (int i = 0; i < n; i++) arr[i] = rand() % 1000000; clock_t start, end; double t; start = clock(); long long r1 = countMissingSorted(arr, n); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Sorted (n=%d): result=%lld, time=%.3f ms\n", n, r1, t); start = clock(); long long r2 = countMissingHash(arr, n); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Hash (n=%d): result=%lld, time=%.3f ms\n", n, r2, t); printf("Verify: %s\n", (r1 == r2) ? "PASS" : "FAIL"); free(arr); } 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("\nMissing count: %lld\n", countMissingHash(arr, n)); free(arr); } int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Missing Elements of a Range Demo ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Demonstrate Both 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
- Sort: Sort, then sum
nxt - cur - 1for adjacent distinct pairs. Duplicates contribute zero, andnxt == cur + 1means consecutive. - Hash: Insert into a set; track
minandmax. The answer is(max - min + 1) - set_size.
Expected Output (sample run)
text
=== Sample Arrays === Test 1: [4,5,3,8,6] Array: [4, 5, 3, 8, 6] Sorted: 1 Hash: 1 Verify: PASS Test 2: [2,1,3] Array: [2, 1, 3] Sorted: 0 Hash: 0 Verify: PASS Test 3: [3,5,8,6] Array: [3, 5, 8, 6] Sorted: 2 Hash: 2 Verify: PASS Test 4: [10,10,10] Array: [10, 10, 10] Sorted: 0 Hash: 0 Verify: PASS Test 5: [1,5,10] Array: [1, 5, 10] Sorted: 6 Hash: 6 Verify: PASS Test 6: [-5,-2,0,1] Array: [-5, -2, 0, 1] Sorted: 3 Hash: 3 Verify: PASS === Edge Cases === Empty array: sorted=0, hash=0 Single element: sorted=0, hash=0 [5,5,5,5]: sorted=0, hash=0 (expect 0) [1..5]: sorted=0, hash=0 (expect 0) [1, 1e9]: sorted=999999998, hash=999999998 (expect 999999998) [1,1,3,5,5,5,7]: sorted=2, hash=2 (expect 2: 2,4,6) [-10,-8,-8,-5]: sorted=3, hash=3 (expect 3)
Common Pitfalls, Edge Cases & Memory Considerations
1. Duplicate Elements Break Naive Gap Counting
Without the nxt > cur + 1 check, adjacent duplicates add -1 per pair, corrupting the count.
c
if (nxt > cur + 1) missing += nxt - cur - 1;
2. Integer Overflow in max - min + 1
For min = INT_MIN and max = INT_MAX, the range overflows int.
Solution: Use long long for range size.
3. Empty and Single-Element Arrays
No range exists; missing count is 0.
4. All Duplicates
The set contains one value; range_size == 1; result 0.
5. All Consecutive
No gap; result 0.
6. Negative Values
Both approaches handle them.
7. Hash Table Sizing
Undersized table → probe failures.
Solution: Size ≥ 2× n.
8. Range Width Overflows long long
For extreme values (min = -9×10¹⁸, max = 9×10¹⁸) even long long may overflow. In such cases, split the difference:
c
unsigned long long width = (unsigned long long)maxv - (unsigned long long)minv + 1;
9. Sorting Mutates Input
Copy before sorting if preservation is needed.
10. Memory Considerations
- Sorted: O(n) for the copy.
- Hash: O(n) for the set.
- Both use
long longfor the result.
Summary & Best Practices
Counting missing elements in the min–max range is a compact set-versus-range problem. The hash-set solution is the cleanest: insert distinct values, compute (max - min + 1) - distinct_count.
Key Takeaways
missing = (max - min + 1) - distinct_count.- Sorted: adjacent gap summation, ignoring duplicates.
- Hash: one pass, set + min/max tracking.
- Both handle negatives, duplicates, and unsorted input.
- Use
long longfor range width.
Best Practices
- Use the hash set for O(n) average.
- Use sorting when memory is tight.
- Use
long longfor range size arithmetic. - Track
min/maxin the same pass as insertion. - Do not add gap counts for duplicates.
- Size hash tables ≥ 2×
n. - Copy inputs before sorting if preservation matters.
- Handle empty/single-element arrays as
0. - Test with negatives, duplicates, and wide gaps.
- Profile for large inputs.
By mastering this problem, you’ll be equipped for set-difference, range-completeness, and gap-counting tasks.
