Tag O(n) algorithm

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

Approach	Time	Space	Notes
Naive nested loops	O(n²)	O(1)	Simple but slow
Sorting	O(n log n)	O(1) or O(n)	Modifies array
Hash set	O(n) avg	O(n)	Extra memory
Sum formula	O(n)	O(1)	Overflow risk
XOR	O(n)	O(1)	No overflow, elegant
Element as index	O(n)	O(1)	Modifies array
Floyd’s cycle detection	O(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.