Tag teacher pointing to a whiteboard chart about finding the missing number in an array

Find the Missing Number in C: A Comprehensive Tutorial

Finding the missing number in an array of distinct integers from 1 to n is a classic algorithmic problem. Given an array of size n-1 containing distinct integers from the range [1, n], exactly one number is missing. This problem tests your understanding of arithmetic sums, bitwise operations, and time-space trade-offs.

This tutorial provides an in-depth exploration of finding the missing number in C: naive linear search, hash-based approach, sum-of-n-terms formula, XOR operation, practical implementation, common pitfalls, and best practices.

---

Conceptual Introduction & Fundamentals

What is the Problem?

Given an array arr[] of size n - 1 containing distinct integers from 1 to n (inclusive), find the missing element.

Examples:

text

Input: arr = [8, 2, 4, 5, 3, 7, 1] Output: 6 Explanation: n = 8, numbers 1 to 8 present except 6. Input: arr = [1, 2, 3, 5] Output: 4 Explanation: n = 5, numbers 1 to 5 present except 4.

Why This Problem Matters

• Arithmetic series: Teaches the sum formula n(n+1)/2.
• Bitwise XOR: Demonstrates cancellation property.
• Algorithm optimization: O(n²) → O(n) with O(1) space.
• Interview preparation: Very common coding interview question.
• Real-world applications: Detecting missing records, sequence gaps.

Approaches Overview

Approach	Time Complexity	Space Complexity
Naive linear search	O(n²)	O(1)
Hash array	O(n)	O(n)
Sum formula	O(n)	O(1)
XOR operation	O(n)	O(1)

Key Insight

Since the array contains all numbers from 1 to n except one:

• Sum approach: Missing = Sum(1..n) - Sum(arr)
• XOR approach: XOR of 1..n and XOR of arr cancel all present numbers, leaving the missing one.

---

Syntax & Core Mechanics

Approach 1: Naive Linear Search

For each number from 1 to n, check if it exists in the array.

c

#include <stdio.h> int findMissingNaive(const int arr[], int n) { /* n is the size of the array; range is 1..n+1 */ int range = n + 1; for (int i = 1; i <= range; i++) { int found = 0; for (int j = 0; j < n; j++) { if (arr[j] == i) { found = 1; break; } } if (!found) return i; } return -1; } int main(void) { int arr[] = {8, 2, 4, 5, 3, 7, 1}; int n = sizeof(arr) / sizeof(arr[0]); printf("Missing number: %d\n", findMissingNaive(arr, n)); return 0; }

Expected output:

text

Missing number: 6

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

Approach 2: Hash Array

Use a boolean array to mark presence.

c

#include <stdio.h> #include <stdlib.h> #include <string.h> int findMissingHash(const int arr[], int n) { int range = n + 1; int *hash = calloc(range + 1, sizeof(int)); if (hash == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return -1; } for (int i = 0; i < n; i++) { hash[arr[i]] = 1; } int result = -1; for (int i = 1; i <= range; i++) { if (hash[i] == 0) { result = i; break; } } free(hash); return result; } int main(void) { int arr[] = {8, 2, 4, 5, 3, 7, 1}; int n = sizeof(arr) / sizeof(arr[0]); printf("Missing number: %d\n", findMissingHash(arr, n)); return 0; }

Expected output:

text

Missing number: 6

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

Approach 3: Sum of n Terms Formula

Compute expected sum and subtract actual sum.

c

#include <stdio.h> int findMissingSum(const int arr[], int n) { int range = n + 1; /* Sum of array elements */ long long sumArr = 0; for (int i = 0; i < n; i++) { sumArr += arr[i]; } /* Expected sum: 1 + 2 + ... + range */ long long expectedSum = (long long)range * (range + 1) / 2; return (int)(expectedSum - sumArr); } int main(void) { int arr[] = {8, 2, 4, 5, 3, 7, 1}; int n = sizeof(arr) / sizeof(arr[0]); printf("Missing number: %d\n", findMissingSum(arr, n)); return 0; }

Expected output:

text

Missing number: 6

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

Approach 4: XOR Operation

XOR all array elements and all numbers from 1 to n+1; the result is the missing number.

c

#include <stdio.h> int findMissingXOR(const int arr[], int n) { int range = n + 1; int xorAll = 0; /* XOR all array elements */ for (int i = 0; i < n; i++) { xorAll ^= arr[i]; } /* XOR all numbers from 1 to range */ for (int i = 1; i <= range; i++) { xorAll ^= i; } return xorAll; } int main(void) { int arr[] = {8, 2, 4, 5, 3, 7, 1}; int n = sizeof(arr) / sizeof(arr[0]); printf("Missing number: %d\n", findMissingXOR(arr, n)); return 0; }

Expected output:

text

Missing number: 6

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

Step-by-Step XOR Trace

text

arr = [8, 2, 4, 5, 3, 7, 1], range = 8 XOR of arr: 8 ^ 2 ^ 4 ^ 5 ^ 3 ^ 7 ^ 1 XOR of 1..8: 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 Combined: (1^1) ^ (2^2) ^ (3^3) ^ (4^4) ^ (5^5) ^ (7^7) ^ 8 ^ 6 = 0 ^ 0 ^ 0 ^ 0 ^ 0 ^ 0 ^ 8 ^ 6 = 8 ^ 6 = 14 ... wait, let's recompute Actually: XOR of arr cancels 1,2,3,4,5,7 with XOR of 1..8 Remaining: 8 (from 1..8) ^ 6 (from 1..8) Wait, 6 isn't in arr, so XOR of 1..8 includes 6. XOR of arr includes 8 (which is also in 1..8). Cancellations: 1,2,3,4,5,7 cancel between the two XORs. Remaining: 6 (from 1..8) and 8 (from arr) ... Hmm, let me redo: XOR of arr = 8 ^ 2 ^ 4 ^ 5 ^ 3 ^ 7 ^ 1 XOR of 1..8 = 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 Combined = (1^1) ^ (2^2) ^ (3^3) ^ (4^4) ^ (5^5) ^ (7^7) ^ 8 ^ 8 ^ 6 = 0 ^ ... ^ 0 ^ 6 = 6 ✓

So the missing number is 6.

---

Full Practical Code Example with Explanation

This program demonstrates all four approaches with verification, performance comparison, and edge cases.

Program: Missing Number Finder

c

/** * missing_number.c * Finds the missing number in an array of distinct integers from 1..n. * Compares naive, hash, sum, and XOR approaches. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <time.h> #define MAX_LINE_LEN 100 #define MAX_SIZE 100000 /* Function prototypes */ int findMissingNaive(const int arr[], int n); int findMissingHash(const int arr[], int n); int findMissingSum(const int arr[], int n); int findMissingXOR(const int arr[], int n); int readInteger(const char *prompt, int *outValue); void printArray(const int arr[], int n); void demonstrateApproaches(void); void performanceComparison(void); void demonstrateEdgeCases(void); int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Missing Number Finder ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Demonstrate All Approaches\n"); printf("2. Custom Array\n"); printf("3. Performance Comparison\n"); printf("4. Edge Cases\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: demonstrateApproaches(); break; case 2: { int arr[MAX_SIZE]; int n; if (readInteger("Enter array size (n-1, 1-99999): ", &n) != 0) { fprintf(stderr, "Invalid size.\n"); break; } if (n < 1 || n > MAX_SIZE) { printf("Size must be 1-%d.\n", MAX_SIZE); break; } printf("Enter %d elements (distinct, from 1 to %d):\n", n, n + 1); for (int i = 0; i < n; i++) { char prompt[50]; snprintf(prompt, sizeof(prompt), " Element %d: ", i); if (readInteger(prompt, &arr[i]) != 0) { fprintf(stderr, "Invalid input.\n"); n = i; break; } } printf("\nArray: "); printArray(arr, n); printf("Range: 1 to %d\n", n + 1); int sumResult = findMissingSum(arr, n); int xorResult = findMissingXOR(arr, n); printf("Missing (sum): %d\n", sumResult); printf("Missing (XOR): %d\n", xorResult); printf("Verification: %s\n", (sumResult == xorResult) ? "PASS" : "FAIL"); break; } case 3: performanceComparison(); break; case 4: demonstrateEdgeCases(); break; case 5: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice. Please try again.\n"); break; } } return EXIT_SUCCESS; } /* Naive: O(n^2) */ int findMissingNaive(const int arr[], int n) { int range = n + 1; for (int i = 1; i <= range; i++) { int found = 0; for (int j = 0; j < n; j++) { if (arr[j] == i) { found = 1; break; } } if (!found) return i; } return -1; } /* Hash array: O(n) time, O(n) space */ int findMissingHash(const int arr[], int n) { int range = n + 1; int *hash = calloc(range + 2, sizeof(int)); if (hash == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return -1; } for (int i = 0; i < n; i++) { if (arr[i] >= 1 && arr[i] <= range) { hash[arr[i]] = 1; } } int result = -1; for (int i = 1; i <= range; i++) { if (hash[i] == 0) { result = i; break; } } free(hash); return result; } /* Sum formula: O(n) time, O(1) space */ int findMissingSum(const int arr[], int n) { int range = n + 1; long long sumArr = 0; for (int i = 0; i < n; i++) { sumArr += arr[i]; } long long expectedSum = (long long)range * (range + 1) / 2; return (int)(expectedSum - sumArr); } /* XOR: O(n) time, O(1) space */ int findMissingXOR(const int arr[], int n) { int range = n + 1; int xorAll = 0; for (int i = 0; i < n; i++) { xorAll ^= arr[i]; } for (int i = 1; i <= range; i++) { xorAll ^= i; } return xorAll; } /* Prints array */ 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("]\n"); } /* Demonstrates all approaches */ void demonstrateApproaches(void) { printf("\n=== Sample Arrays ===\n"); int arr1[] = {8, 2, 4, 5, 3, 7, 1}; int n1 = sizeof(arr1) / sizeof(arr1[0]); printf("\nArray 1: "); printArray(arr1, n1); printf("Range: 1..%d\n", n1 + 1); printf("Naive: %d\n", findMissingNaive(arr1, n1)); printf("Hash: %d\n", findMissingHash(arr1, n1)); printf("Sum: %d\n", findMissingSum(arr1, n1)); printf("XOR: %d\n", findMissingXOR(arr1, n1)); int arr2[] = {1, 2, 3, 5}; int n2 = sizeof(arr2) / sizeof(arr2[0]); printf("\nArray 2: "); printArray(arr2, n2); printf("Range: 1..%d\n", n2 + 1); printf("Naive: %d\n", findMissingNaive(arr2, n2)); printf("Hash: %d\n", findMissingHash(arr2, n2)); printf("Sum: %d\n", findMissingSum(arr2, n2)); printf("XOR: %d\n", findMissingXOR(arr2, n2)); int arr3[] = {1}; int n3 = sizeof(arr3) / sizeof(arr3[0]); printf("\nArray 3 (n=1): "); printArray(arr3, n3); printf("Range: 1..2\n"); printf("Naive: %d\n", findMissingNaive(arr3, n3)); printf("Hash: %d\n", findMissingHash(arr3, n3)); printf("Sum: %d\n", findMissingSum(arr3, n3)); printf("XOR: %d\n", findMissingXOR(arr3, n3)); int arr4[] = {2, 3, 4, 5}; int n4 = sizeof(arr4) / sizeof(arr4[0]); printf("\nArray 4: "); printArray(arr4, n4); printf("Range: 1..%d\n", n4 + 1); printf("Sum: %d\n", findMissingSum(arr4, n4)); printf("XOR: %d\n", findMissingXOR(arr4, n4)); } /* Performance comparison */ void performanceComparison(void) { printf("\n=== Performance Comparison (n = 1000000) ===\n"); int n = 1000000; int *arr = malloc(n * sizeof(int)); if (arr == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return; } /* Fill 1..n+1 except missing n/2 */ int missing = n / 2; int idx = 0; for (int i = 1; i <= n + 1; i++) { if (i != missing) { arr[idx++] = i; } } clock_t start, end; double timeTaken; /* Hash */ start = clock(); int hashResult = findMissingHash(arr, n); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Hash (O(n)): Result = %d, Time = %.3f ms\n", hashResult, timeTaken); /* Sum */ start = clock(); int sumResult = findMissingSum(arr, n); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Sum (O(n)): Result = %d, Time = %.3f ms\n", sumResult, timeTaken); /* XOR */ start = clock(); int xorResult = findMissingXOR(arr, n); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("XOR (O(n)): Result = %d, Time = %.3f ms\n", xorResult, timeTaken); printf("\nVerification: %s\n", (sumResult == xorResult && xorResult == hashResult) ? "PASS" : "FAIL"); free(arr); } /* Demonstrates edge cases */ void demonstrateEdgeCases(void) { printf("\n=== Edge Cases ===\n"); /* Case 1: Single element, missing 1 */ int arr1[] = {2}; printf("Case 1: n=1, missing 1\n"); printf(" Array: "); printArray(arr1, 1); printf(" Sum: %d, XOR: %d\n", findMissingSum(arr1, 1), findMissingXOR(arr1, 1)); /* Case 2: Single element, missing 2 */ int arr2[] = {1}; printf("\nCase 2: n=1, missing 2\n"); printf(" Array: "); printArray(arr2, 1); printf(" Sum: %d, XOR: %d\n", findMissingSum(arr2, 1), findMissingXOR(arr2, 1)); /* Case 3: Missing 1 */ int arr3[] = {2, 3, 4, 5}; printf("\nCase 3: Missing 1\n"); printf(" Array: "); printArray(arr3, 4); printf(" Sum: %d, XOR: %d\n", findMissingSum(arr3, 4), findMissingXOR(arr3, 4)); /* Case 4: Missing n+1 */ int arr4[] = {1, 2, 3, 4}; printf("\nCase 4: Missing last (n+1)\n"); printf(" Array: "); printArray(arr4, 4); printf(" Sum: %d, XOR: %d\n", findMissingSum(arr4, 4), findMissingXOR(arr4, 4)); /* Case 5: Large array */ int n5 = 1000; int *arr5 = malloc(n5 * sizeof(int)); if (arr5 == NULL) return; for (int i = 1; i <= n5; i++) { arr5[i - 1] = i; } /* Missing n5+1 */ printf("\nCase 5: Large array, missing %d\n", n5 + 1); printf(" Sum: %d, XOR: %d\n", findMissingSum(arr5, n5), findMissingXOR(arr5, n5)); free(arr5); /* Case 6: Overflow check */ int n6 = 100000; int *arr6 = malloc(n6 * sizeof(int)); if (arr6 == NULL) return; for (int i = 1; i <= n6; i++) { arr6[i - 1] = i; } /* Missing n6+1 */ printf("\nCase 6: Overflow-safe with long long (n=%d, missing %d)\n", n6, n6 + 1); printf(" Sum: %d, XOR: %d\n", findMissingSum(arr6, n6), findMissingXOR(arr6, n6)); free(arr6); } /* Reads an integer safely */ 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; }

Explanation of Approaches

1. Naive: Checks each number 1..n+1 against the array; O(n²).
2. Hash: Uses a boolean array to mark presence; O(n) time, O(n) space.
3. Sum: Uses arithmetic series formula; O(n) time, O(1) space.
4. XOR: Cancels pairs leaving the missing number; O(n) time, O(1) space.

Expected Output (sample run)

text

=== Missing Number Finder === --- Menu --- 1. Demonstrate All Approaches 2. Custom Array 3. Performance Comparison 4. Edge Cases 5. Exit Enter choice: 1 === Sample Arrays === Array 1: [8, 2, 4, 5, 3, 7, 1] Range: 1..8 Naive: 6 Hash: 6 Sum: 6 XOR: 6 Array 2: [1, 2, 3, 5] Range: 1..5 Naive: 4 Hash: 4 Sum: 4 XOR: 4 Array 3 (n=1): [1] Range: 1..2 Naive: 2 Hash: 2 Sum: 2 XOR: 2 Array 4: [2, 3, 4, 5] Range: 1..5 Sum: 1 XOR: 1 --- Menu --- ... Enter choice: 4 === Edge Cases === Case 1: n=1, missing 1 Array: [2] Sum: 1, XOR: 1 Case 2: n=1, missing 2 Array: [1] Sum: 2, XOR: 2 Case 3: Missing 1 Array: [2, 3, 4, 5] Sum: 1, XOR: 1 Case 4: Missing last (n+1) Array: [1, 2, 3, 4] Sum: 5, XOR: 5 Case 5: Large array, missing 1001 Sum: 1001, XOR: 1001 Case 6: Overflow-safe with long long (n=100000, missing 100001) Sum: 100001, XOR: 100001

---

Common Pitfalls, Edge Cases & Memory Considerations

1. Off-by-One in Range

If the array size is n, the range is 1..n+1 (not 1..n).

c

int range = n + 1; /* Correct: array has n elements from 1..n+1 */

2. Integer Overflow in Sum

n × (n+1) / 2 can overflow int for large n.

c

long long expectedSum = (long long)range * (range + 1) / 2;

3. Order of Operations for Overflow

(range * (range + 1)) / 2 may overflow before dividing. Cast first.

c

(long long)range * (range + 1) / 2 /* Safe */

4. Empty Array

For an empty array, the missing number is 1 (range 1..1).

c

int arr[] = {}; /* Missing = 1 */

5. Single Element

If the array has one element, the range is 1..2.

c

int arr[] = {1}; /* Missing = 2 */ int arr[] = {2}; /* Missing = 1 */

6. Missing First (1)

Works correctly with both sum and XOR.

c

int arr[] = {2, 3, 4}; /* Missing = 1 */

7. Missing Last (n+1)

Works correctly with both sum and XOR.

c

int arr[] = {1, 2, 3}; /* Missing = 4 */

8. Duplicate Values (Invalid Input)

The problem guarantees distinct integers. Duplicates break the assumptions.

9. Values Out of Range (Invalid Input)

The problem guarantees values in [1, n+1]. Invalid input breaks the algorithm.

10. Memory Considerations

• Naive: O(1) extra space.
• Hash: O(n) extra space.
• Sum: O(1) extra space.
• XOR: O(1) extra space — preferred for memory and avoiding overflow.
• Use long long for sums when n is large.

---

Summary & Best Practices

Finding the missing number in an array of distinct integers from 1..n is elegantly solved using either the sum formula or XOR. XOR is preferred for avoiding overflow; sum is preferred for simplicity.

Key Takeaways

• Array has n elements; range is 1..n+1.
• Sum formula: Missing = n(n+1)/2 - Sum(arr).
• XOR: XOR all elements and 1..n+1; result is missing.
• Naive: O(n²) time, O(1) space.
• Hash: O(n) time, O(n) space.
• Sum/XOR: O(n) time, O(1) space — optimal.
• Use long long for sums to prevent overflow.

Best Practices

1. Use XOR for O(n) time, O(1) space, and no overflow risk.
2. Use sum formula for simplicity when n is small.
3. Use long long for the sum to prevent overflow.
4. Handle edge cases: empty, single element, missing first, missing last.
5. Verify the problem’s guarantees (distinct, in-range values).
6. Use hash when the problem allows duplicates or values outside the range.
7. Document the formula in comments.
8. Test with n = 1 and large n.
9. Profile for very large arrays.
10. Avoid int overflow in intermediate computations.

By mastering this problem, you’ll understand arithmetic series and XOR cancellation, applicable to many array and bitwise problems.