Tag bitwise operations

Missing and Repeating in an Array in C: A Comprehensive Tutorial

Given an unsorted array of size n containing elements from the range 1 to n, exactly one number is missing and another appears twice. The task is to find both the duplicate (repeating) and the missing number. This is a classic algorithmic problem that tests your understanding of array manipulation, mathematical equations, bitwise operations, and time-space trade-offs.

This tutorial provides an in-depth exploration of finding both the missing and repeating numbers in C: visited array approach, array marking, two math equations, XOR approach, practical implementation, common pitfalls, and best practices.

---

Conceptual Introduction & Fundamentals

What is the Problem?

Given an array arr[] of size n with elements from the range [1, n]:

• Exactly one number appears twice (repeating).
• Exactly one number is missing.
• All other numbers appear exactly once.

Find both the repeating and missing numbers.

Examples:

text

Input: [3, 1, 3] Output: [3, 2] (3 repeats, 2 is missing) Input: [4, 3, 6, 2, 1, 1] Output: [1, 5] (1 repeats, 5 is missing)

Why This Problem Matters

• Multiple approaches: Demonstrates trade-offs between time and space.
• Mathematical reasoning: Sum and sum-of-squares equations.
• Bitwise operations: XOR-based grouping technique.
• Interview preparation: Very common coding interview question.
• Real-world applications: Data integrity, duplicate detection, sequence validation.

Approaches Overview

Approach	Time Complexity	Space Complexity
Visited array	O(n)	O(n)
Array marking (negation)	O(n)	O(1)
Two math equations	O(n)	O(1)
XOR	O(n)	O(1)

---

Syntax & Core Mechanics

Approach 1: Visited Array (Frequency Count)

Use a frequency array to count occurrences.

c

#include <stdio.h> #include <stdlib.h> #include <string.h> void findTwoElement(const int arr[], int n, int *repeating, int *missing) { int *freq = calloc(n + 1, sizeof(int)); if (freq == NULL) { fprintf(stderr, "Memory allocation failed.\n"); *repeating = -1; *missing = -1; return; } for (int i = 0; i < n; i++) { freq[arr[i]]++; } *repeating = -1; *missing = -1; for (int i = 1; i <= n; i++) { if (freq[i] == 0) *missing = i; else if (freq[i] == 2) *repeating = i; } free(freq); } int main(void) { int arr[] = {3, 1, 3}; int n = sizeof(arr) / sizeof(arr[0]); int repeating, missing; findTwoElement(arr, n, &repeating, &missing); printf("Repeating: %d, Missing: %d\n", repeating, missing); return 0; }

Expected output:

text

Repeating: 3, Missing: 2

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

Approach 2: Array Marking (Negation)

Use the input array itself to track visited elements by negating values.

c

#include <stdio.h> #include <stdlib.h> void findTwoElement(const int arr[], int n, int *repeating, int *missing) { int *copy = malloc(n * sizeof(int)); if (copy == NULL) { *repeating = -1; *missing = -1; return; } memcpy(copy, arr, n * sizeof(int)); *repeating = -1; /* Mark visited by negating */ for (int i = 0; i < n; i++) { int val = abs(copy[i]); if (copy[val - 1] > 0) { copy[val - 1] = -copy[val - 1]; } else { *repeating = val; /* Already visited */ } } *missing = -1; for (int i = 0; i < n; i++) { if (copy[i] > 0) { *missing = i + 1; break; } } free(copy); } int main(void) { int arr[] = {3, 1, 3}; int n = sizeof(arr) / sizeof(arr[0]); int repeating, missing; findTwoElement(arr, n, &repeating, &missing); printf("Repeating: %d, Missing: %d\n", repeating, missing); return 0; }

Expected output:

text

Repeating: 3, Missing: 2

Time: O(n), Space: O(n) for copy (O(1) if input can be modified)

Approach 3: Two Math Equations

Use sum and sum-of-squares formulas.

Derivation:

text

Let x = missing, y = repeating. Sum equation: x - y = S_expected - S_actual (call it s) Squares equation: x² - y² = SS_expected - SS_actual (call it ssq) From squares: (x - y)(x + y) = ssq → (x + y) = ssq / s Solving: x = (s + ssq/s) / 2 y = x - s

c

#include <stdio.h> void findTwoElement(const int arr[], int n, int *repeating, int *missing) { long long s = (long long)n * (n + 1) / 2; long long ssq = (long long)n * (n + 1) * (2 * n + 1) / 6; for (int i = 0; i < n; i++) { s -= arr[i]; ssq -= (long long)arr[i] * arr[i]; } *missing = (int)((s + ssq / s) / 2); *repeating = (int)(*missing - s); } int main(void) { int arr[] = {3, 1, 3}; int n = sizeof(arr) / sizeof(arr[0]); int repeating, missing; findTwoElement(arr, n, &repeating, &missing); printf("Repeating: %d, Missing: %d\n", repeating, missing); return 0; }

Expected output:

text

Repeating: 3, Missing: 2

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

Approach 4: XOR

XOR all array elements and numbers 1..n to get x ^ y. Use a set bit to divide into groups.

c

#include <stdio.h> void findTwoElement(const int arr[], int n, int *repeating, int *missing) { int xorVal = 0; for (int i = 0; i < n; i++) { xorVal ^= arr[i]; xorVal ^= (i + 1); } int setBit = xorVal & ~(xorVal - 1); int x = 0, y = 0; for (int i = 0; i < n; i++) { if (arr[i] & setBit) x ^= arr[i]; else y ^= arr[i]; if ((i + 1) & setBit) x ^= (i + 1); else y ^= (i + 1); } /* Determine which is which */ int xCount = 0; for (int i = 0; i < n; i++) { if (arr[i] == x) xCount++; } if (xCount == 0) { *missing = x; *repeating = y; } else { *missing = y; *repeating = x; } } int main(void) { int arr[] = {3, 1, 3}; int n = sizeof(arr) / sizeof(arr[0]); int repeating, missing; findTwoElement(arr, n, &repeating, &missing); printf("Repeating: %d, Missing: %d\n", repeating, missing); return 0; }

Expected output:

text

Repeating: 3, Missing: 2

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

---

Full Practical Code Example with Explanation

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

Program: Missing and Repeating Finder

c

/** * missing_repeating.c * Finds both missing and repeating numbers in an array. * Compares visited array, marking, math, 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 */ void findVisited(const int arr[], int n, int *repeating, int *missing); void findMarking(const int arr[], int n, int *repeating, int *missing); void findMath(const int arr[], int n, int *repeating, int *missing); void findXOR(const int arr[], int n, int *repeating, int *missing); 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 and Repeating 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 (1-100000): ", &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 (1..%d, one missing, one repeated):\n", n, n); 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); int rep, mis; findVisited(arr, n, &rep, &mis); printf("Visited: Repeating = %d, Missing = %d\n", rep, mis); findMarking(arr, n, &rep, &mis); printf("Marking: Repeating = %d, Missing = %d\n", rep, mis); findMath(arr, n, &rep, &mis); printf("Math: Repeating = %d, Missing = %d\n", rep, mis); findXOR(arr, n, &rep, &mis); printf("XOR: Repeating = %d, Missing = %d\n", rep, mis); 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; } /* Approach 1: Visited array */ void findVisited(const int arr[], int n, int *repeating, int *missing) { int *freq = calloc(n + 1, sizeof(int)); if (freq == NULL) { *repeating = -1; *missing = -1; return; } for (int i = 0; i < n; i++) { if (arr[i] >= 1 && arr[i] <= n) { freq[arr[i]]++; } } *repeating = -1; *missing = -1; for (int i = 1; i <= n; i++) { if (freq[i] == 0) *missing = i; else if (freq[i] == 2) *repeating = i; } free(freq); } /* Approach 2: Array marking (negation) */ void findMarking(const int arr[], int n, int *repeating, int *missing) { int *copy = malloc(n * sizeof(int)); if (copy == NULL) { *repeating = -1; *missing = -1; return; } memcpy(copy, arr, n * sizeof(int)); *repeating = -1; for (int i = 0; i < n; i++) { int val = abs(copy[i]); if (val >= 1 && val <= n) { if (copy[val - 1] > 0) { copy[val - 1] = -copy[val - 1]; } else { *repeating = val; } } } *missing = -1; for (int i = 0; i < n; i++) { if (copy[i] > 0) { *missing = i + 1; break; } } free(copy); } /* Approach 3: Math equations */ void findMath(const int arr[], int n, int *repeating, int *missing) { long long s = (long long)n * (n + 1) / 2; long long ssq = (long long)n * (n + 1) * (2 * n + 1) / 6; for (int i = 0; i < n; i++) { s -= arr[i]; ssq -= (long long)arr[i] * arr[i]; } if (s == 0) { *repeating = -1; *missing = -1; return; } *missing = (int)((s + ssq / s) / 2); *repeating = (int)(*missing - s); } /* Approach 4: XOR */ void findXOR(const int arr[], int n, int *repeating, int *missing) { int xorVal = 0; for (int i = 0; i < n; i++) { xorVal ^= arr[i]; xorVal ^= (i + 1); } int setBit = xorVal & ~(xorVal - 1); int x = 0, y = 0; for (int i = 0; i < n; i++) { if (arr[i] & setBit) x ^= arr[i]; else y ^= arr[i]; if ((i + 1) & setBit) x ^= (i + 1); else y ^= (i + 1); } int xCount = 0; for (int i = 0; i < n; i++) { if (arr[i] == x) xCount++; } if (xCount == 0) { *missing = x; *repeating = y; } else { *missing = y; *repeating = x; } } /* 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[] = {3, 1, 3}; int n1 = sizeof(arr1) / sizeof(arr1[0]); int rep, mis; printf("\nArray 1: "); printArray(arr1, n1); findVisited(arr1, n1, &rep, &mis); printf(" Visited: Rep=%d, Mis=%d\n", rep, mis); findMarking(arr1, n1, &rep, &mis); printf(" Marking: Rep=%d, Mis=%d\n", rep, mis); findMath(arr1, n1, &rep, &mis); printf(" Math: Rep=%d, Mis=%d\n", rep, mis); findXOR(arr1, n1, &rep, &mis); printf(" XOR: Rep=%d, Mis=%d\n", rep, mis); int arr2[] = {4, 3, 6, 2, 1, 1}; int n2 = sizeof(arr2) / sizeof(arr2[0]); printf("\nArray 2: "); printArray(arr2, n2); findVisited(arr2, n2, &rep, &mis); printf(" Visited: Rep=%d, Mis=%d\n", rep, mis); findMarking(arr2, n2, &rep, &mis); printf(" Marking: Rep=%d, Mis=%d\n", rep, mis); findMath(arr2, n2, &rep, &mis); printf(" Math: Rep=%d, Mis=%d\n", rep, mis); findXOR(arr2, n2, &rep, &mis); printf(" XOR: Rep=%d, Mis=%d\n", rep, mis); } /* Performance comparison */ void performanceComparison(void) { printf("\n=== Performance Comparison (n = 100000) ===\n"); int n = 100000; int *arr = malloc(n * sizeof(int)); if (arr == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return; } /* Fill 1..n, replace one with duplicate of another */ int missing = n / 2; int repeat = n / 3; for (int i = 0; i < n; i++) { arr[i] = i + 1; } /* Replace missing with repeat */ for (int i = 0; i < n; i++) { if (arr[i] == missing) { arr[i] = repeat; break; } } clock_t start, end; double timeTaken; int rep, mis; start = clock(); findVisited(arr, n, &rep, &mis); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Visited: Rep=%d, Mis=%d, Time = %.3f ms\n", rep, mis, timeTaken); start = clock(); findMarking(arr, n, &rep, &mis); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Marking: Rep=%d, Mis=%d, Time = %.3f ms\n", rep, mis, timeTaken); start = clock(); findMath(arr, n, &rep, &mis); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Math: Rep=%d, Mis=%d, Time = %.3f ms\n", rep, mis, timeTaken); start = clock(); findXOR(arr, n, &rep, &mis); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("XOR: Rep=%d, Mis=%d, Time = %.3f ms\n", rep, mis, timeTaken); free(arr); } /* Demonstrates edge cases */ void demonstrateEdgeCases(void) { printf("\n=== Edge Cases ===\n"); int rep, mis; /* Case 1: n = 2 */ int arr1[] = {1, 1}; printf("Case 1: n=2, [1, 1]\n"); findVisited(arr1, 2, &rep, &mis); printf(" Visited: Rep=%d, Mis=%d\n", rep, mis); findMath(arr1, 2, &rep, &mis); printf(" Math: Rep=%d, Mis=%d\n", rep, mis); findXOR(arr1, 2, &rep, &mis); printf(" XOR: Rep=%d, Mis=%d\n", rep, mis); /* Case 2: Repeat at start */ int arr2[] = {1, 1, 2, 3}; printf("\nCase 2: Repeat at start\n"); printf(" Array: "); printArray(arr2, 4); findMath(arr2, 4, &rep, &mis); printf(" Math: Rep=%d, Mis=%d\n", rep, mis); findXOR(arr2, 4, &rep, &mis); printf(" XOR: Rep=%d, Mis=%d\n", rep, mis); /* Case 3: Repeat at end */ int arr3[] = {1, 2, 3, 3}; printf("\nCase 3: Repeat at end\n"); printf(" Array: "); printArray(arr3, 4); findMath(arr3, 4, &rep, &mis); printf(" Math: Rep=%d, Mis=%d\n", rep, mis); findXOR(arr3, 4, &rep, &mis); printf(" XOR: Rep=%d, Mis=%d\n", rep, mis); /* Case 4: Missing 1 */ int arr4[] = {2, 2, 3, 4}; printf("\nCase 4: Missing 1\n"); printf(" Array: "); printArray(arr4, 4); findXOR(arr4, 4, &rep, &mis); printf(" XOR: Rep=%d, Mis=%d\n", rep, mis); /* Case 5: Missing n */ int arr5[] = {1, 1, 2, 3}; printf("\nCase 5: Missing n (4)\n"); printf(" Array: "); printArray(arr5, 4); findXOR(arr5, 4, &rep, &mis); printf(" XOR: Rep=%d, Mis=%d\n", rep, mis); } /* 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. Visited: Uses a frequency array; O(n) time, O(n) space.
2. Marking: Negates visited indices in a copy; O(n) time, O(n) space (or O(1) if input is mutable).
3. Math: Uses sum and sum-of-squares equations; O(n) time, O(1) space.
4. XOR: Divides elements into groups by a set bit; O(n) time, O(1) space.

Expected Output (sample run)

text

=== Missing and Repeating 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: [3, 1, 3] Visited: Rep=3, Mis=2 Marking: Rep=3, Mis=2 Math: Rep=3, Mis=2 XOR: Rep=3, Mis=2 Array 2: [4, 3, 6, 2, 1, 1] Visited: Rep=1, Mis=5 Marking: Rep=1, Mis=5 Math: Rep=1, Mis=5 XOR: Rep=1, Mis=5 --- Menu --- ... Enter choice: 4 === Edge Cases === Case 1: n=2, [1, 1] Visited: Rep=1, Mis=2 Math: Rep=1, Mis=2 XOR: Rep=1, Mis=2 Case 2: Repeat at start Array: [1, 1, 2, 3] Math: Rep=1, Mis=4 XOR: Rep=1, Mis=4 Case 3: Repeat at end Array: [1, 2, 3, 3] Math: Rep=3, Mis=4 XOR: Rep=3, Mis=4 Case 4: Missing 1 Array: [2, 2, 3, 4] XOR: Rep=2, Mis=1 Case 5: Missing n (4) Array: [1, 1, 2, 3] XOR: Rep=1, Mis=4

---

Common Pitfalls, Edge Cases & Memory Considerations

1. Integer Overflow in Math Approach

n × (n+1) × (2n+1) / 6 overflows quickly for large n.

c

long long ssq = (long long)n * (n + 1) * (2 * n + 1) / 6; /* Cast */

Solution: Use long long and cast before multiplication.

2. Division by Zero in Math Approach

If s == 0 (no missing/repeating, invalid input), division fails.

c

if (s == 0) { /* handle invalid input */ }

3. Array Marking Modifies Input

The marking approach requires modifying the array (or a copy).

Solution: Copy the array first if preservation is needed.

4. XOR Determination of Missing vs Repeating

XOR gives two values; must determine which is which by counting occurrences.

c

int xCount = 0; for (int i = 0; i < n; i++) { if (arr[i] == x) xCount++; } if (xCount == 0) { /* x is missing, y is repeating */ }

5. Zero Values in Array

Problem specifies values in [1, n]; zero values are invalid input.

6. n = 1 Edge Case

If n = 1, the array has one element, and that element must be the repeating one (missing 1).

c

int arr[] = {1}; /* Repeating = 1, Missing = 2 ... but n=1 means values in [1,1] */ /* Actually the problem requires n >= 2 */

Solution: Handle n == 1 explicitly if needed.

7. Duplicate Values Beyond Two

Problem guarantees exactly one repeat; other inputs break the algorithm.

8. Hash Array Sizing

Ensure frequency array size is n + 1 (indices 0..n).

9. Memory Leaks

Free dynamically allocated frequency arrays.

10. Memory Considerations

• Visited: O(n) extra space.
• Marking: O(n) extra space (or O(1) if mutating input).
• Math: O(1) extra space.
• XOR: O(1) extra space — preferred for memory.
• Use long long for math approach.

---

Summary & Best Practices

Finding the missing and repeating numbers in an array is solved elegantly using XOR (O(n) time, O(1) space) or math equations (O(n) time, O(1) space). Both approaches avoid extra memory.

Key Takeaways

• Array has n elements from range 1..n.
• One element repeats; one is missing.
• Visited: O(n) time, O(n) space.
• Marking: O(n) time, O(1)-O(n) space.
• Math: O(n) time, O(1) space (watch for overflow).
• XOR: O(n) time, O(1) space — preferred.

Best Practices

1. Use XOR for O(n) time and O(1) space without overflow.
2. Use math for simplicity when n is small.
3. Use long long for math to prevent overflow.
4. Use visited array for clarity when memory permits.
5. Verify with multiple approaches during testing.
6. Handle edge cases: n=2, missing/repeat at boundaries.
7. Free dynamically allocated memory.
8. Validate input (values in [1, n], exactly one repeat).
9. Test with n=2 and larger values.
10. Profile for large arrays.

By mastering this problem, you’ll understand multiple algorithmic techniques and their trade-offs, applicable to many array and bitwise problems.