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 element
• max = maximum element
• range_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

1. Sort: Sort, then sum nxt - cur - 1 for adjacent distinct pairs. Duplicates contribute zero, and nxt == cur + 1 means consecutive.
2. Hash: Insert into a set; track min and max. 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 long for 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 long for range width.

Best Practices

1. Use the hash set for O(n) average.
2. Use sorting when memory is tight.
3. Use long long for range size arithmetic.
4. Track min/max in the same pass as insertion.
5. Do not add gap counts for duplicates.
6. Size hash tables ≥ 2× n.
7. Copy inputs before sorting if preservation matters.
8. Handle empty/single-element arrays as 0.
9. Test with negatives, duplicates, and wide gaps.
10. Profile for large inputs.

By mastering this problem, you’ll be equipped for set-difference, range-completeness, and gap-counting tasks.