CoreTechED

Loading

Tag Floyd cycle detection

Learn 7 ways to find the only repeating element from 1 to n-1 in C: naive, sort, hash, sum, XOR, index marking, and Floyd's cycle detection.
C Programming

Find the Only Repeating Element 1 to n-1 in C

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

ApproachTimeSpaceMutates Input?
Naive nested loopsO(n²)O(1)No
SortingO(n log n)O(1) or O(n)Optional
Hash setO(n)O(n)No
Sum formulaO(n)O(1)No
XORO(n)O(1)No
Index markingO(n)O(1)Yes
Floyd’s cycleO(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.

Learn to find the only repeating element in an array from 1 to n-1 in C: naive, sorting, hash, sum, XOR, marking, and Floyd's cycle detection.
C Programming

Find Only Repeating Element 1 to n-1 in C

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

Given an array of size n filled with numbers from 1 to n-1 in random order, where exactly one number repeats, the task is to find that repeating element. This classic problem tests your understanding of multiple algorithmic techniques—from naive nested loops to elegant bitwise and mathematical solutions.

This tutorial provides an in-depth exploration of finding the only repeating element in C: naive nested loops, sorting, hash set, sum formula, XOR, element-as-index marking, Floyd’s cycle detection, practical implementation, common pitfalls, and best practices.

Conceptual Introduction & Fundamentals

What is the Problem?

Given an array arr[] of size n containing numbers from 1 to n-1, where exactly one number appears twice and all others appear once, find the repeating element.

Examples:

text

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

Why This Problem Matters

  • Multiple approaches: Demonstrates trade-offs between time and space.
  • Bitwise operations: XOR cancellation property.
  • Mathematical reasoning: Sum of first n-1 natural numbers.
  • Cycle detection: Floyd’s algorithm adaptation.
  • Interview preparation: Very common coding interview question.

Approaches Overview

ApproachTimeSpaceNotes
Naive nested loopsO(n²)O(1)Simple but slow
SortingO(n log n)O(1) or O(n)Modifies array
Hash setO(n) avgO(n)Extra memory
Sum formulaO(n)O(1)Overflow risk
XORO(n)O(1)No overflow, elegant
Element as indexO(n)O(1)Modifies array
Floyd’s cycle detectionO(n)O(1)Read-only, advanced

Syntax & Core Mechanics

Approach 1: Naive Nested Loops

Check each element against subsequent elements.

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("Duplicate: %d\n", findDuplicateNaive(arr, n)); return 0; }

Expected output:

text

Duplicate: 3

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

Approach 2: Sorting

Sort the array; the duplicate will be adjacent.

c

#include <stdio.h> #include <stdlib.h> int compareInts(const void *a, const void *b) { int int_a = *(const int *)a; int int_b = *(const int *)b; return (int_a > int_b) - (int_a < int_b); } int findDuplicateSorted(int arr[], int n) { qsort(arr, n, sizeof(int), compareInts); for (int i = 0; i < n - 1; i++) { if (arr[i] == arr[i + 1]) { return arr[i]; } } return -1; } int main(void) { int arr[] = {1, 3, 2, 3, 4}; int n = sizeof(arr) / sizeof(arr[0]); printf("Duplicate: %d\n", findDuplicateSorted(arr, n)); return 0; }

Expected output:

text

Duplicate: 3

Time: O(n log n), Space: O(1) (in-place)

Approach 3: Hash Set

Track visited elements; return on second encounter.

c

#include <stdio.h> #include <stdlib.h> #define TABLE_SIZE 4096 typedef struct { int *keys; int *occupied; int capacity; } HashSet; HashSet *createHashSet(int capacity) { HashSet *set = malloc(sizeof(HashSet)); if (set == NULL) return NULL; set->keys = malloc(capacity * sizeof(int)); set->occupied = calloc(capacity, sizeof(int)); if (set->keys == NULL || set->occupied == NULL) { free(set->keys); free(set->occupied); free(set); return NULL; } set->capacity = capacity; return set; } void freeHashSet(HashSet *set) { if (set != NULL) { free(set->keys); free(set->occupied); free(set); } } int hashFunc(int key, int cap) { return ((key % cap) + cap) % cap; } int contains(HashSet *set, int key) { int idx = hashFunc(key, set->capacity); int start = idx; while (set->occupied[idx]) { if (set->keys[idx] == key) return 1; idx = (idx + 1) % set->capacity; if (idx == start) break; } return 0; } void insert(HashSet *set, int key) { int idx = hashFunc(key, set->capacity); int start = idx; while (set->occupied[idx]) { if (set->keys[idx] == key) return; idx = (idx + 1) % set->capacity; if (idx == start) return; } set->keys[idx] = key; set->occupied[idx] = 1; } int findDuplicateHash(const int arr[], int n) { HashSet *set = createHashSet(TABLE_SIZE); if (set == NULL) return -1; int result = -1; for (int i = 0; i < n; i++) { if (contains(set, arr[i])) { result = arr[i]; break; } insert(set, arr[i]); } freeHashSet(set); return result; } int main(void) { int arr[] = {1, 3, 2, 3, 4}; int n = sizeof(arr) / sizeof(arr[0]); printf("Duplicate: %d\n", findDuplicateHash(arr, n)); return 0; }

Expected output:

text

Duplicate: 3

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

Approach 4: Sum Formula

Sum of 1..n-1 is (n-1)*n/2. Subtract from actual sum.

c

#include <stdio.h> int 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 (int)(sum - expected); } int main(void) { int arr[] = {1, 3, 2, 3, 4}; int n = sizeof(arr) / sizeof(arr[0]); printf("Duplicate: %d\n", findDuplicateSum(arr, n)); return 0; }

Expected output:

text

Duplicate: 3

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

Approach 5: XOR

XOR of 1..n-1 and all array elements; pairs cancel, leaving the duplicate.

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("Duplicate: %d\n", findDuplicateXOR(arr, n)); return 0; }

Expected output:

text

Duplicate: 3

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

Approach 6: Element as Index (Marking)

Negate the value at the index equal to the element’s value.

c

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

Expected output:

text

Duplicate: 3

Time: O(n), Space: O(1) — modifies array

Note: This approach assumes values are in [1, n-1] so arr[val] is always a valid index.

Approach 7: Floyd’s Cycle Detection

Treat the array as a linked list where arr[i] is the next pointer.

c

#include <stdio.h> int findDuplicateFloyd(const int arr[], int n) { int slow = arr[0]; int fast = arr[0]; /* Phase 1: Find meeting point */ do { slow = arr[slow]; fast = arr[arr[fast]]; } while (slow != fast); /* Phase 2: Find cycle entry (duplicate) */ 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("Duplicate: %d\n", findDuplicateFloyd(arr, n)); return 0; }

Expected output:

text

Duplicate: 3

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

Full Practical Code Example with Explanation

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

Program: Duplicate Finder Comparison

c

/** * only_repeating.c * Finds the only repeating element in array of 1..n-1. * Compares all major 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 findDuplicateNaive(const int arr[], int n); int findDuplicateSorted(int arr[], int n); int findDuplicateHash(const int arr[], int n); int findDuplicateSum(const int arr[], int n); int findDuplicateXOR(const int arr[], int n); int findDuplicateMarking(int arr[], int n); int findDuplicateFloyd(const int arr[], int n); int compareInts(const void *a, const void *b); 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("=== Only Repeating Element Finder (1..n-1) ===\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 copy[MAX_SIZE]; int n; if (readInteger("Enter array size (2-100000): ", &n) != 0) { fprintf(stderr, "Invalid size.\n"); break; } if (n < 2 || n > MAX_SIZE) { printf("Size must be 2-%d.\n", MAX_SIZE); break; } printf("Enter %d elements (1..%d, one repeated):\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); memcpy(copy, arr, n * sizeof(int)); printf("Naive: %d\n", findDuplicateNaive(arr, n)); memcpy(copy, arr, n * sizeof(int)); printf("Sorted: %d\n", findDuplicateSorted(copy, n)); printf("Hash: %d\n", findDuplicateHash(arr, n)); printf("Sum: %d\n", findDuplicateSum(arr, n)); printf("XOR: %d\n", findDuplicateXOR(arr, n)); memcpy(copy, arr, n * sizeof(int)); printf("Marking: %d\n", findDuplicateMarking(copy, n)); printf("Floyd: %d\n", findDuplicateFloyd(arr, n)); 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 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; } /* Comparison function */ int compareInts(const void *a, const void *b) { int int_a = *(const int *)a; int int_b = *(const int *)b; return (int_a > int_b) - (int_a < int_b); } /* Sorting: O(n log n) */ int findDuplicateSorted(int arr[], int n) { qsort(arr, n, sizeof(int), compareInts); for (int i = 0; i < n - 1; i++) { if (arr[i] == arr[i + 1]) return arr[i]; } return -1; } /* Hash set: O(n) average */ #define TABLE_SIZE 4096 typedef struct { int *keys; int *occupied; int capacity; } HashSet; HashSet *createHashSet(int capacity) { HashSet *set = malloc(sizeof(HashSet)); if (set == NULL) return NULL; set->keys = malloc(capacity * sizeof(int)); set->occupied = calloc(capacity, sizeof(int)); if (set->keys == NULL || set->occupied == NULL) { free(set->keys); free(set->occupied); free(set); return NULL; } set->capacity = capacity; return set; } void freeHashSet(HashSet *set) { if (set != NULL) { free(set->keys); free(set->occupied); free(set); } } int hashFunc(int key, int cap) { return ((key % cap) + cap) % cap; } int contains(HashSet *set, int key) { int idx = hashFunc(key, set->capacity); int start = idx; while (set->occupied[idx]) { if (set->keys[idx] == key) return 1; idx = (idx + 1) % set->capacity; if (idx == start) break; } return 0; } void insert(HashSet *set, int key) { int idx = hashFunc(key, set->capacity); int start = idx; while (set->occupied[idx]) { if (set->keys[idx] == key) return; idx = (idx + 1) % set->capacity; if (idx == start) return; } set->keys[idx] = key; set->occupied[idx] = 1; } int findDuplicateHash(const int arr[], int n) { HashSet *set = createHashSet(TABLE_SIZE); if (set == NULL) return -1; int result = -1; for (int i = 0; i < n; i++) { if (contains(set, arr[i])) { result = arr[i]; break; } insert(set, arr[i]); } freeHashSet(set); return result; } /* Sum formula: O(n) */ int 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 (int)(sum - expected); } /* XOR: O(n) */ 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; } /* Marking: O(n), modifies array */ int findDuplicateMarking(int arr[], int n) { for (int i = 0; i < n; i++) { int val = abs(arr[i]); if (val < 1 || val > n - 1) continue; if (arr[val] < 0) return val; arr[val] = -arr[val]; } return -1; } /* Floyd's cycle detection: O(n), read-only */ 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; } /* 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[] = {1, 3, 2, 3, 4}; int n1 = sizeof(arr1) / sizeof(arr1[0]); int copy[MAX_SIZE]; printf("\nArray 1: "); printArray(arr1, n1); printf("Naive: %d\n", findDuplicateNaive(arr1, n1)); memcpy(copy, arr1, n1 * sizeof(int)); printf("Sorted: %d\n", findDuplicateSorted(copy, n1)); printf("Hash: %d\n", findDuplicateHash(arr1, n1)); printf("Sum: %d\n", findDuplicateSum(arr1, n1)); printf("XOR: %d\n", findDuplicateXOR(arr1, n1)); memcpy(copy, arr1, n1 * sizeof(int)); printf("Marking: %d\n", findDuplicateMarking(copy, n1)); printf("Floyd: %d\n", findDuplicateFloyd(arr1, n1)); int arr2[] = {1, 5, 1, 2, 3, 4}; int n2 = sizeof(arr2) / sizeof(arr2[0]); printf("\nArray 2: "); printArray(arr2, n2); printf("Sum: %d\n", findDuplicateSum(arr2, n2)); printf("XOR: %d\n", findDuplicateXOR(arr2, n2)); printf("Floyd: %d\n", findDuplicateFloyd(arr2, n2)); } /* Performance comparison */ void performanceComparison(void) { printf("\n=== Performance Comparison (n = 100000) ===\n"); int n = 100000; int *arr = malloc(n * sizeof(int)); int *copy = malloc(n * sizeof(int)); if (arr == NULL || copy == NULL) { fprintf(stderr, "Memory allocation failed.\n"); free(arr); free(copy); return; } /* Fill 1..n-1 plus duplicate n/2 */ int dup = n / 2; for (int i = 0; i < n - 1; i++) arr[i] = i + 1; arr[n - 1] = dup; clock_t start, end; double timeTaken; memcpy(copy, arr, n * sizeof(int)); start = clock(); int sortedResult = findDuplicateSorted(copy, n); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Sorted: Result = %d, Time = %.3f ms\n", sortedResult, timeTaken); start = clock(); int hashResult = findDuplicateHash(arr, n); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Hash: Result = %d, Time = %.3f ms\n", hashResult, timeTaken); start = clock(); int sumResult = findDuplicateSum(arr, n); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Sum: Result = %d, Time = %.3f ms\n", sumResult, timeTaken); start = clock(); int xorResult = findDuplicateXOR(arr, n); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("XOR: Result = %d, Time = %.3f ms\n", xorResult, timeTaken); memcpy(copy, arr, n * sizeof(int)); start = clock(); int markResult = findDuplicateMarking(copy, n); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Marking: Result = %d, Time = %.3f ms\n", markResult, timeTaken); start = clock(); int floydResult = findDuplicateFloyd(arr, n); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Floyd: Result = %d, Time = %.3f ms\n", floydResult, timeTaken); printf("\nVerification: %s\n", (sumResult == xorResult && xorResult == floydResult && floydResult == hashResult) ? "PASS" : "FAIL"); free(arr); free(copy); } /* Demonstrates edge cases */ void demonstrateEdgeCases(void) { printf("\n=== Edge Cases ===\n"); int copy[MAX_SIZE]; /* Case 1: n=2, duplicate 1 */ int arr1[] = {1, 1}; printf("Case 1: n=2, [1, 1]\n"); printf(" XOR: %d\n", findDuplicateXOR(arr1, 2)); printf(" Sum: %d\n", findDuplicateSum(arr1, 2)); printf(" Floyd: %d\n", findDuplicateFloyd(arr1, 2)); /* Case 2: Duplicate at start */ int arr2[] = {1, 1, 2, 3}; printf("\nCase 2: Duplicate at start\n"); printf(" Array: "); printArray(arr2, 4); printf(" XOR: %d\n", findDuplicateXOR(arr2, 4)); printf(" Floyd: %d\n", findDuplicateFloyd(arr2, 4)); /* Case 3: Duplicate at end */ int arr3[] = {1, 2, 3, 3}; printf("\nCase 3: Duplicate at end\n"); printf(" Array: "); printArray(arr3, 4); printf(" XOR: %d\n", findDuplicateXOR(arr3, 4)); printf(" Floyd: %d\n", findDuplicateFloyd(arr3, 4)); /* Case 4: Duplicate is max (n-1) */ int arr4[] = {1, 2, 4, 3, 4}; printf("\nCase 4: Duplicate is max\n"); printf(" Array: "); printArray(arr4, 5); printf(" XOR: %d\n", findDuplicateXOR(arr4, 5)); printf(" Floyd: %d\n", findDuplicateFloyd(arr4, 5)); /* Case 5: Duplicate is 1 in larger array */ int arr5[] = {2, 3, 1, 4, 1}; printf("\nCase 5: Duplicate is 1\n"); printf(" Array: "); printArray(arr5, 5); printf(" XOR: %d\n", findDuplicateXOR(arr5, 5)); printf(" Floyd: %d\n", findDuplicateFloyd(arr5, 5)); /* Case 6: Marking approach demonstration */ int arr6[] = {1, 3, 2, 3, 4}; memcpy(copy, arr6, 5 * sizeof(int)); printf("\nCase 6: Marking approach\n"); printf(" Array: "); printArray(copy, 5); printf(" Marking: %d\n", findDuplicateMarking(copy, 5)); } /* 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: O(n²) nested loops.
  2. Sorting: O(n log n), adjacent duplicates.
  3. Hash: O(n) average, O(n) space.
  4. Sum: O(n) time, O(1) space, arithmetic formula.
  5. XOR: O(n) time, O(1) space, no overflow.
  6. Marking: O(n) time, O(1) space, modifies array.
  7. Floyd’s: O(n) time, O(1) space, read-only.

Expected Output (sample run)

text

=== Only Repeating Element Finder (1..n-1) === --- Menu --- 1. Demonstrate All Approaches 2. Custom Array 3. Performance Comparison 4. Edge Cases 5. Exit Enter choice: 1 === Sample Arrays === Array 1: [1, 3, 2, 3, 4] Naive: 3 Sorted: 3 Hash: 3 Sum: 3 XOR: 3 Marking: 3 Floyd: 3 Array 2: [1, 5, 1, 2, 3, 4] Sum: 1 XOR: 1 Floyd: 1 --- Menu --- ... Enter choice: 4 === Edge Cases === Case 1: n=2, [1, 1] XOR: 1 Sum: 1 Floyd: 1 Case 2: Duplicate at start Array: [1, 1, 2, 3] XOR: 1 Floyd: 1 Case 3: Duplicate at end Array: [1, 2, 3, 3] XOR: 3 Floyd: 3 Case 4: Duplicate is max Array: [1, 2, 4, 3, 4] XOR: 4 Floyd: 4 Case 5: Duplicate is 1 Array: [2, 3, 1, 4, 1] XOR: 1 Floyd: 1 Case 6: Marking approach Array: [1, 3, 2, 3, 4] Marking: 3

Common Pitfalls, Edge Cases & Memory Considerations

1. Confusing n and Range

Array size is n; values are in [1, n-1]. Sum formula uses (n-1)*n/2.

2. Integer Overflow in Sum

For large n, sum may overflow int.

c

long long sum = 0; /* Use long long */

3. Off-by-One in XOR

XOR loops 1..n-1 and all array elements (including duplicate).

c

for (int i = 0; i < n - 1; i++) { res ^= (i + 1); res ^= arr[i]; } res ^= arr[n - 1]; /* Last element */

4. Marking Approach Requires In-Range Values

If any value is outside [1, n-1], marking accesses invalid indices.

Solution: Validate input or skip out-of-range values.

5. Marking Modifies Array

Preserve original if needed by copying.

6. Floyd’s Requires Valid Index Chain

Array must be such that arr[0] doesn’t cause out-of-bounds.

Solution: Problem guarantees values in [1, n-1]; arr[0] is safe.

7. n = 2 Edge Case

Array size 2, values [1, 1] (only possible duplicate).

8. Empty Array

Invalid input; problem requires n ≥ 2.

9. Duplicate at Index 0

Works with all approaches; Floyd starts at arr[0].

10. Memory Considerations

  • Naive: O(1) extra space.
  • Sorting: O(1) extra space (in-place).
  • Hash: O(n) extra space.
  • Sum: O(1) extra space.
  • XOR: O(1) extra space — preferred.
  • Marking: O(1) extra space, modifies input.
  • Floyd: O(1) extra space, read-only — most elegant.

Summary & Best Practices

Finding the only repeating element in an array from 1..n-1 is elegantly solved using XOR (O(n), O(1), no overflow) or Floyd’s cycle detection (O(n), O(1), read-only). Both avoid extra memory.

Key Takeaways

  • Array size n, values [1, n-1], one duplicate.
  • Naive: O(n²).
  • Sorting: O(n log n).
  • Hash: O(n) time, O(n) space.
  • Sum: O(n) time, O(1) space (overflow risk).
  • XOR: O(n) time, O(1) space — preferred.
  • Marking: O(n) time, O(1) space, modifies array.
  • Floyd’s: O(n) time, O(1) space, read-only.

Best Practices

  1. Use XOR for O(n) time, O(1) space, no overflow.
  2. Use Floyd’s when input must not be modified.
  3. Use sum formula for simplicity when n is small.
  4. Use hash set when other approaches aren’t applicable.
  5. Use long long for sum to prevent overflow.
  6. Verify with multiple approaches during testing.
  7. Handle edge cases: n=2, duplicate at boundaries.
  8. Free dynamically allocated memory.
  9. Validate input (values in [1, n-1]).
  10. Profile for large arrays.

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