Tag O(n) algorithm

Find the Only Repeating Element From 1 to n-1 in C: A Comprehensive Tutorial

Given an array of size n containing numbers from 1 to n-1 in random order, exactly one number repeats. Finding that duplicate without extra memory is a canonical problem that showcases six distinct algorithms—from brute force to Floyd’s cycle detection. It’s a favorite in coding interviews because each solution reveals a different algorithmic idea.

This tutorial explores all six approaches in C with portable C99/C11 code, robust error handling, and complete expected outputs.

---

Conceptual Introduction & Fundamentals

What is the Problem?

An array arr[] of size n contains values from 1 to n-1 (each appearing once) except for one value that appears twice. Find the duplicate.

Examples:

text

Input: [1, 3, 2, 3, 4] Output: 3 Input: [1, 5, 1, 2, 3, 4] Output: 1

Why This Problem Matters

• Six distinct approaches: Naive, sort, hash set, sum, XOR, index-marking, Floyd’s.
• Bit manipulation: XOR cancellation property.
• Cycle detection: Floyd’s tortoise-and-hare on array-as-linked-list.
• In-place mutation: Index marking without extra memory.
• Interview preparation: Extremely common problem.

Approaches Overview

Approach	Time	Space	Mutates Input?
Naive nested loops	O(n²)	O(1)	No
Sorting	O(n log n)	O(1) or O(n)	Optional
Hash set	O(n)	O(n)	No
Sum formula	O(n)	O(1)	No
XOR	O(n)	O(1)	No
Index marking	O(n)	O(1)	Yes
Floyd’s cycle	O(n)	O(1)	No

Key Insights

• Sum formula: duplicate = sum(arr) - n(n-1)/2
• XOR: duplicate = XOR(arr) ⊕ XOR(1..n-1)
• Index marking: Negate arr[|arr[i]|]; the repeated sign flip identifies the duplicate.
• Floyd’s: Treat arr[i] as a pointer to the next node; the duplicate is the cycle entry.

---

Syntax & Core Mechanics

Approach 1: Naive Nested Loops

Compare every pair (i, j) with i < j.

c

#include <stdio.h> int findDuplicateNaive(const int arr[], int n) { for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (arr[i] == arr[j]) return arr[i]; } } return -1; } int main(void) { int arr[] = {1, 3, 2, 3, 4}; int n = sizeof(arr) / sizeof(arr[0]); printf("%d\n", findDuplicateNaive(arr, n)); return 0; }

Expected output:

text

3

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

Approach 2: Sort + Adjacent Scan

Sort then check adjacent pairs.

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 findDuplicateSorted(const int arr_in[], int n) { if (n < 2) 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 res = -1; for (int i = 0; i < n - 1; i++) { if (arr[i] == arr[i + 1]) { res = arr[i]; break; } } free(arr); return res; } int main(void) { int arr[] = {1, 3, 2, 3, 4}; int n = sizeof(arr) / sizeof(arr[0]); printf("%d\n", findDuplicateSorted(arr, n)); return 0; }

Expected output:

text

3

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

Approach 3: Hash Set

Track seen elements.

c

#include <stdio.h> #include <stdlib.h> #define TABLE_SIZE 2048 typedef struct { int *keys; int *occupied; int capacity; } 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; return s; } void freeSet(HashSet *s) { if (s) { free(s->keys); free(s->occupied); free(s); } } int setContains(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 1; idx = (idx + 1) % (unsigned int)s->capacity; if ((int)idx == start) break; } return 0; } 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; return 1; } int findDuplicateHash(const int arr[], int n) { HashSet *s = createSet(TABLE_SIZE); if (s == NULL) return -1; int res = -1; for (int i = 0; i < n; i++) { if (setContains(s, arr[i])) { res = arr[i]; break; } setInsert(s, arr[i]); } freeSet(s); return res; } int main(void) { int arr[] = {1, 3, 2, 3, 4}; int n = sizeof(arr) / sizeof(arr[0]); printf("%d\n", findDuplicateHash(arr, n)); return 0; }

Expected output:

text

3

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

Approach 4: Sum Formula

The duplicate equals the difference between the array sum and 1 + 2 + ... + (n-1).

c

#include <stdio.h> long long findDuplicateSum(const int arr[], int n) { long long sum = 0; for (int i = 0; i < n; i++) sum += arr[i]; long long expected = (long long)(n - 1) * n / 2; return sum - expected; } int main(void) { int arr[] = {1, 3, 2, 3, 4}; int n = sizeof(arr) / sizeof(arr[0]); printf("%lld\n", findDuplicateSum(arr, n)); return 0; }

Expected output:

text

3

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

Approach 5: XOR

XOR of 1..n-1 and the array cancels non-duplicates.

c

#include <stdio.h> int findDuplicateXOR(const int arr[], int n) { int res = 0; for (int i = 0; i < n - 1; i++) { res ^= (i + 1); res ^= arr[i]; } res ^= arr[n - 1]; return res; } int main(void) { int arr[] = {1, 3, 2, 3, 4}; int n = sizeof(arr) / sizeof(arr[0]); printf("%d\n", findDuplicateXOR(arr, n)); return 0; }

Expected output:

text

3

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

Approach 6: Index Marking

Negate the value at index |arr[i]|. The second time we visit a negated index, we’ve found the duplicate.

c

#include <stdio.h> #include <stdlib.h> int findDuplicateMarking(int arr[], int n) { for (int i = 0; i < n; i++) { int idx = abs(arr[i]); if (idx < 1 || idx >= n) continue; /* Safety */ if (arr[idx] < 0) return idx; arr[idx] = -arr[idx]; } return -1; } int main(void) { int arr[] = {1, 3, 2, 3, 4}; int n = sizeof(arr) / sizeof(arr[0]); printf("%d\n", findDuplicateMarking(arr, n)); return 0; }

Expected output:

text

3

Time: O(n), Space: O(1) — but mutates input

Approach 7: Floyd’s Cycle Detection

Treat the array as a linked list where arr[i] is the next node. The duplicate is the cycle entry.

c

#include <stdio.h> int findDuplicateFloyd(const int arr[], int n) { int slow = arr[0]; int fast = arr[0]; do { slow = arr[slow]; fast = arr[arr[fast]]; } while (slow != fast); fast = arr[0]; while (slow != fast) { slow = arr[slow]; fast = arr[fast]; } return slow; } int main(void) { int arr[] = {1, 3, 2, 3, 4}; int n = sizeof(arr) / sizeof(arr[0]); printf("%d\n", findDuplicateFloyd(arr, n)); return 0; }

Expected output:

text

3

Time: O(n), Space: O(1), Read-only

---

Full Practical Code Example with Explanation

This program implements all seven approaches and cross-verifies their results on multiple datasets.

c

/** * find_duplicate.c * Finds the only repeating element in arr[] with values 1..n-1. * Implements and compares seven 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 /* ---------- 1. Naive ---------- */ int findDuplicateNaive(const int arr[], int n) { for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if (arr[i] == arr[j]) return arr[i]; return -1; } /* ---------- 2. Sorting ---------- */ 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 findDuplicateSorted(const int arr_in[], int n) { if (n < 2) 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 res = -1; for (int i = 0; i < n - 1; i++) { if (arr[i] == arr[i + 1]) { res = arr[i]; break; } } free(arr); return res; } /* ---------- 3. Hash Set ---------- */ typedef struct { int *keys; int *occupied; int capacity; } 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; return s; } void freeSet(HashSet *s) { if (s) { free(s->keys); free(s->occupied); free(s); } } int setContains(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 1; idx = (idx + 1) % (unsigned int)s->capacity; if ((int)idx == start) break; } return 0; } 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; return 1; } int findDuplicateHash(const int arr[], int n) { HashSet *s = createSet(TABLE_SIZE); if (s == NULL) return -1; int res = -1; for (int i = 0; i < n; i++) { if (setContains(s, arr[i])) { res = arr[i]; break; } setInsert(s, arr[i]); } freeSet(s); return res; } /* ---------- 4. Sum ---------- */ long long findDuplicateSum(const int arr[], int n) { long long sum = 0; for (int i = 0; i < n; i++) sum += arr[i]; return sum - (long long)(n - 1) * n / 2; } /* ---------- 5. XOR ---------- */ int findDuplicateXOR(const int arr[], int n) { int res = 0; for (int i = 0; i < n - 1; i++) { res ^= (i + 1); res ^= arr[i]; } res ^= arr[n - 1]; return res; } /* ---------- 6. Index Marking ---------- */ int findDuplicateMarking(int arr[], int n) { for (int i = 0; i < n; i++) { int idx = arr[i] < 0 ? -arr[i] : arr[i]; if (idx < 1 || idx >= n) continue; if (arr[idx] < 0) return idx; arr[idx] = -arr[idx]; } return -1; } /* ---------- 7. Floyd's Cycle Detection ---------- */ int findDuplicateFloyd(const int arr[], int n) { int slow = arr[0]; int fast = arr[0]; do { slow = arr[slow]; fast = arr[arr[fast]]; } while (slow != fast); fast = arr[0]; while (slow != fast) { slow = arr[slow]; fast = arr[fast]; } return slow; } /* ---------- 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, 3, 2, 3, 4}; int a2[] = {1, 5, 1, 2, 3, 4}; int a3[] = {2, 2}; int a4[] = {1, 2, 3, 4, 5, 3}; struct { int *arr; int n; const char *label; } tests[] = { {a1, 5, "arr=[1,3,2,3,4]"}, {a2, 6, "arr=[1,5,1,2,3,4]"}, {a3, 2, "arr=[2,2]"}, {a4, 6, "arr=[1,2,3,4,5,3]"} }; 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 = findDuplicateNaive(tests[t].arr, tests[t].n); int r2 = findDuplicateSorted(tests[t].arr, tests[t].n); int r3 = findDuplicateHash(tests[t].arr, tests[t].n); long long r4 = findDuplicateSum(tests[t].arr, tests[t].n); int r5 = findDuplicateXOR(tests[t].arr, tests[t].n); /* Index marking and Floyd require mutable / non-negative inputs */ int *copy = malloc((size_t)tests[t].n * sizeof(int)); memcpy(copy, tests[t].arr, (size_t)tests[t].n * sizeof(int)); int r6 = findDuplicateMarking(copy, tests[t].n); free(copy); int r7 = findDuplicateFloyd(tests[t].arr, tests[t].n); printf(" Naive: %d\n", r1); printf(" Sorted: %d\n", r2); printf(" Hash: %d\n", r3); printf(" Sum: %lld\n", r4); printf(" XOR: %d\n", r5); printf(" Index mark: %d\n", r6); printf(" Floyd: %d\n", r7); int ok = (r1 == r2 && r2 == r3 && r3 == (int)r4 && r5 == r6 && r6 == r7 && r7 == r1); printf(" Verify: %s\n", ok ? "PASS" : "FAIL"); } printf("\n"); } static void demoEdgeCases(void) { printf("\n=== Edge Cases ===\n"); /* n = 2, duplicate = 1 */ int a1[] = {1, 1}; printf("[1,1] → naive=%d, hash=%d, sum=%lld, xor=%d, floyd=%d\n", findDuplicateNaive(a1, 2), findDuplicateHash(a1, 2), findDuplicateSum(a1, 2), findDuplicateXOR(a1, 2), findDuplicateFloyd(a1, 2)); /* Duplicate at start */ int a2[] = {3, 3, 1, 2}; printf("[3,3,1,2] → naive=%d, hash=%d, sum=%lld, xor=%d\n", findDuplicateNaive(a2, 4), findDuplicateHash(a2, 4), findDuplicateSum(a2, 4), findDuplicateXOR(a2, 4)); /* Duplicate at end */ int a3[] = {1, 2, 3, 3}; printf("[1,2,3,3] → naive=%d, hash=%d, sum=%lld, xor=%d\n", findDuplicateNaive(a3, 4), findDuplicateHash(a3, 4), findDuplicateSum(a3, 4), findDuplicateXOR(a3, 4)); /* Largest possible duplicate */ int a4[] = {1, 2, 3, 4, 5, 5}; printf("[1..5,5] → sum=%lld, xor=%d, floyd=%d\n", findDuplicateSum(a4, 6), findDuplicateXOR(a4, 6), findDuplicateFloyd(a4, 6)); /* Duplicate in the middle */ int a5[] = {1, 2, 4, 4, 3}; printf("[1,2,4,4,3] → sum=%lld, xor=%d, floyd=%d\n", findDuplicateSum(a5, 5), findDuplicateXOR(a5, 5), findDuplicateFloyd(a5, 5)); /* Single possible n (n=2) with duplicate 1 */ int a6[] = {1, 1}; printf("[1,1] floyd=%d (self-loop)\n", findDuplicateFloyd(a6, 2)); } static void performanceTest(void) { printf("\n=== Performance Comparison ===\n"); /* Naive small */ int smallN = 3000; int *smallArr = malloc((size_t)smallN * sizeof(int)); if (smallArr == NULL) return; for (int i = 0; i < smallN - 1; i++) smallArr[i] = i + 1; smallArr[smallN - 1] = smallN / 2; /* Duplicate n/2 */ clock_t start, end; double t; start = clock(); int r1 = findDuplicateNaive(smallArr, 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 = findDuplicateSorted(smallArr, 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 = findDuplicateHash(smallArr, 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); start = clock(); long long r4 = findDuplicateSum(smallArr, smallN); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Sum (n=%d): result=%lld, time=%.3f ms\n", smallN, r4, t); start = clock(); int r5 = findDuplicateXOR(smallArr, smallN); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("XOR (n=%d): result=%d, time=%.3f ms\n", smallN, r5, t); int *copy = malloc((size_t)smallN * sizeof(int)); memcpy(copy, smallArr, (size_t)smallN * sizeof(int)); start = clock(); int r6 = findDuplicateMarking(copy, smallN); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Index mark (n=%d): result=%d, time=%.3f ms\n", smallN, r6, t); free(copy); start = clock(); int r7 = findDuplicateFloyd(smallArr, smallN); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Floyd (n=%d): result=%d, time=%.3f ms\n", smallN, r7, t); int ok = (r1 == r2 && r2 == r3 && r3 == (int)r4 && r5 == r6 && r6 == r7 && r7 == r1); printf("Verify: %s\n", ok ? "PASS" : "FAIL"); free(smallArr); /* Large */ int largeN = 10000000; int *largeArr = malloc((size_t)largeN * sizeof(int)); if (largeArr == NULL) return; for (int i = 0; i < largeN - 1; i++) largeArr[i] = i + 1; largeArr[largeN - 1] = largeN / 2; start = clock(); int r8 = findDuplicateXOR(largeArr, largeN); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("XOR (n=%d): result=%d, time=%.3f ms\n", largeN, r8, t); start = clock(); int r9 = findDuplicateFloyd(largeArr, largeN); end = clock(); t = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Floyd (n=%d): result=%d, time=%.3f ms\n", largeN, r9, t); free(largeArr); } int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Find the Only Repeating Element 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. 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: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice.\n"); break; } } return EXIT_SUCCESS; }

Explanation of Each Approach

1. Naive: O(n²) pair check.
2. Sorted: O(n log n) sort + adjacent scan.
3. Hash set: O(n) with O(n) space.
4. Sum: duplicate = sum - n(n-1)/2.
5. XOR: duplicate = XOR(arr) ⊕ XOR(1..n-1).
6. Index marking: Negate values at their index; the second visit reveals the duplicate.
7. Floyd’s: arr[i] acts as a pointer; the cycle entry is the duplicate.

Expected Output (sample run)

text

=== Sample Arrays === Test 1: arr=[1,3,2,3,4] Array: [1, 3, 2, 3, 4] Naive: 3 Sorted: 3 Hash: 3 Sum: 3 XOR: 3 Index mark: 3 Floyd: 3 Verify: PASS Test 2: arr=[1,5,1,2,3,4] Array: [1, 5, 1, 2, 3, 4] Naive: 1 ... Verify: PASS Test 3: arr=[2,2] ... Test 4: arr=[1,2,3,4,5,3] ... === Edge Cases === [1,1] → naive=1, hash=1, sum=1, xor=1, floyd=1 [3,3,1,2] → naive=3, hash=3, sum=3, xor=3 [1,2,3,3] → naive=3, hash=3, sum=3, xor=3 [1..5,5] → sum=5, xor=5, floyd=5 [1,2,4,4,3] → sum=4, xor=4, floyd=4 [1,1] floyd=1 (self-loop)

---

Common Pitfalls, Edge Cases & Memory Considerations

1. Integer Overflow in Sum

n(n-1)/2 grows quickly.

Solution: Use long long for the sum and expected value.

2. Modifying const Inputs

Index marking mutates the input. Copy if preservation is required.

3. Out-of-Range Values

Index marking requires values in [1, n-1]. Guard with a range check.

c

if (idx < 1 || idx >= n) continue;

4. n = 2 Self-Loop

With [1, 1], Floyd’s algorithm terminates immediately because arr[0] == arr[1] creates a direct self-loop; the result is 1.

5. Floyd’s Requires Values ≤ n-1

The values must be valid indices (i.e., < n). Otherwise the pointer jumps out of bounds.

6. Zero Values

The problem assumes positive values. Zero would break index marking.

7. Hash Table Sizing

Size ≥ 2× n.

8. Sorting Stability

Not required; we only need any duplicate.

9. Mutation During Verification

In multi-approach demos, always copy before running the mutating approach (index marking).

10. Memory Considerations

• Naive, sum, XOR, Floyd: O(1) extra space.
• Sorted: O(n) for copy.
• Hash: O(n) for the set.
• Index marking: O(1) but mutates input.

---

Summary & Best Practices

Finding the only repeating element in [1, n-1] is a rich problem that admits many elegant solutions. XOR and Floyd’s cycle detection are the most impressive read-only, O(1)-space approaches; the sum formula is the simplest; index marking is the fastest in practice but mutates the array.

Key Takeaways

• Values are 1..n-1; exactly one duplicate.
• Sum: duplicate = sum - n(n-1)/2.
• XOR: cancels non-duplicates.
• Index marking: negation-based detection.
• Floyd’s: treats the array as a linked list.
• All O(n) approaches avoid quadratic time.

Best Practices

1. Use XOR for O(n) time and O(1) space without mutation.
2. Use Floyd’s when you want O(1) space and read-only access.
3. Use the sum formula for the simplest solution.
4. Use index marking when mutation is acceptable and speed matters.
5. Use long long for sums to avoid overflow.
6. Guard index marking with a range check.
7. Copy before mutation when demonstrating multiple approaches.
8. Handle n=2 (self-loop in Floyd’s).
9. Free allocated memory.
10. Profile with the largest possible inputs.

By mastering all seven approaches, you’ll be prepared for a wide range of duplicate-detection and cycle-detection problems.