Tag unique element

Unique Number in an Array (Every Element Appears Twice Except One) in C

Finding the unique element in an array where every other element appears exactly twice is a classic problem that tests your understanding of bitwise operations and algorithm optimization. This problem demonstrates the elegant power of XOR and is a favorite in coding interviews.

This tutorial provides an in-depth exploration of finding the unique number in C: naive nested-loop approach, hash-map approach, XOR approach, practical implementation, common pitfalls, and best practices.

---

Conceptual Introduction & Fundamentals

What is the Problem?

Given an array of integers where every element appears exactly twice except for one element that appears only once, find that unique element.

Examples:

text

Input: [2, 3, 5, 4, 5, 3, 4] Output: 2 Input: [2, 2, 5, 5, 20, 30, 30] Output: 20

Why This Problem Matters

• Bitwise operations: Demonstrates XOR’s cancellation property.
• Algorithm optimization: O(n²) → O(n) → O(n) with O(1) space.
• Interview preparation: Extremely common coding interview question.
• Memory efficiency: XOR approach uses no extra memory.
• Foundation for advanced problems: Single Number II, III, and related variants.

Key Insight: XOR Cancellation Property

XOR (exclusive OR) has these properties:

Property	Formula
Identity	a ⊕ 0 = a
Self-inverse	a ⊕ a = 0
Commutative	a ⊕ b = b ⊕ a
Associative	(a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)

When we XOR all elements, pairs cancel out:

text

2 ⊕ 3 ⊕ 5 ⊕ 4 ⊕ 5 ⊕ 3 ⊕ 4 = 2 ⊕ (3 ⊕ 3) ⊕ (5 ⊕ 5) ⊕ (4 ⊕ 4) = 2 ⊕ 0 ⊕ 0 ⊕ 0 = 2

Approaches Overview

Approach	Time Complexity	Space Complexity
Naive frequency count	O(n²)	O(1)
Hash map	O(n)	O(n)
XOR	O(n)	O(1)

---

Syntax & Core Mechanics

Approach 1: Naive Nested Loops

Count occurrences of each element using nested loops.

c

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

Expected output:

text

Unique element: 2

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

Approach 2: Hash Map

Use a hash table to count frequencies, then find the element with count 1.

c

#include <stdio.h> #include <stdlib.h> #define TABLE_SIZE 2048 typedef struct { int *keys; int *counts; int *occupied; int capacity; } HashMap; HashMap *createHashMap(int capacity) { HashMap *map = malloc(sizeof(HashMap)); if (map == NULL) return NULL; map->keys = malloc(capacity * sizeof(int)); map->counts = calloc(capacity, sizeof(int)); map->occupied = calloc(capacity, sizeof(int)); if (map->keys == NULL || map->counts == NULL || map->occupied == NULL) { free(map->keys); free(map->counts); free(map->occupied); free(map); return NULL; } map->capacity = capacity; return map; } void freeHashMap(HashMap *map) { if (map != NULL) { free(map->keys); free(map->counts); free(map->occupied); free(map); } } int hashFunc(int key, int capacity) { return ((key % capacity) + capacity) % capacity; } void increment(HashMap *map, int key) { int idx = hashFunc(key, map->capacity); int start = idx; while (map->occupied[idx]) { if (map->keys[idx] == key) { map->counts[idx]++; return; } idx = (idx + 1) % map->capacity; if (idx == start) return; } map->keys[idx] = key; map->counts[idx] = 1; map->occupied[idx] = 1; } int getCount(HashMap *map, int key) { int idx = hashFunc(key, map->capacity); int start = idx; while (map->occupied[idx]) { if (map->keys[idx] == key) return map->counts[idx]; idx = (idx + 1) % map->capacity; if (idx == start) break; } return 0; } int findUniqueHash(const int arr[], int n) { if (n <= 0) return -1; HashMap *map = createHashMap(TABLE_SIZE); if (map == NULL) return -1; for (int i = 0; i < n; i++) { increment(map, arr[i]); } int result = -1; for (int i = 0; i < n; i++) { if (getCount(map, arr[i]) == 1) { result = arr[i]; break; } } freeHashMap(map); return result; } int main(void) { int arr[] = {2, 3, 5, 4, 5, 3, 4}; int n = sizeof(arr) / sizeof(arr[0]); printf("Unique element: %d\n", findUniqueHash(arr, n)); return 0; }

Expected output:

text

Unique element: 2

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

Approach 3: XOR (Optimal)

XOR all elements; pairs cancel, leaving the unique element.

c

#include <stdio.h> int findUniqueXOR(const int arr[], int n) { int result = 0; for (int i = 0; i < n; i++) { result ^= arr[i]; } return result; } int main(void) { int arr[] = {2, 3, 5, 4, 5, 3, 4}; int n = sizeof(arr) / sizeof(arr[0]); printf("Unique element: %d\n", findUniqueXOR(arr, n)); return 0; }

Expected output:

text

Unique element: 2

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

Step-by-Step XOR Trace

text

arr = [2, 3, 5, 4, 5, 3, 4] result = 0 result ^= 2 → 2 result ^= 3 → 1 result ^= 5 → 4 result ^= 4 → 0 result ^= 5 → 5 result ^= 3 → 6 result ^= 4 → 2 Final: 2 ✓

---

Full Practical Code Example with Explanation

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

Program: Unique Element Finder

c

/** * unique_number.c * Finds the unique element where all others appear twice. * Compares naive, hash map, and XOR approaches. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <time.h> #define MAX_LINE_LEN 100 #define MAX_SIZE 100000 /* Function prototypes */ int findUniqueNaive(const int arr[], int n); int findUniqueHash(const int arr[], int n); int findUniqueXOR(const int arr[], int n); int readInteger(const char *prompt, int *outValue); void printArray(const int arr[], int n); void demonstrateApproaches(void); void performanceComparison(void); void demonstrateEdgeCases(void); int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Unique 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 (odd, 1-99999): ", &n) != 0) { fprintf(stderr, "Invalid size.\n"); break; } if (n < 1 || n > MAX_SIZE) { printf("Size must be 1-%d.\n", MAX_SIZE); break; } printf("Enter %d elements:\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 xorResult = findUniqueXOR(arr, n); printf("Unique element (XOR): %d\n", xorResult); 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 findUniqueNaive(const int arr[], int n) { for (int i = 0; i < n; i++) { int count = 0; for (int j = 0; j < n; j++) { if (arr[i] == arr[j]) count++; } if (count == 1) return arr[i]; } return -1; } /* Hash map: O(n) average */ typedef struct { int *keys; int *counts; int *occupied; int capacity; } HashMap; HashMap *createHashMap(int capacity) { HashMap *map = malloc(sizeof(HashMap)); if (map == NULL) return NULL; map->keys = malloc(capacity * sizeof(int)); map->counts = calloc(capacity, sizeof(int)); map->occupied = calloc(capacity, sizeof(int)); if (map->keys == NULL || map->counts == NULL || map->occupied == NULL) { free(map->keys); free(map->counts); free(map->occupied); free(map); return NULL; } map->capacity = capacity; return map; } void freeHashMap(HashMap *map) { if (map != NULL) { free(map->keys); free(map->counts); free(map->occupied); free(map); } } int hashFunc(int key, int capacity) { return ((key % capacity) + capacity) % capacity; } void increment(HashMap *map, int key) { int idx = hashFunc(key, map->capacity); int start = idx; while (map->occupied[idx]) { if (map->keys[idx] == key) { map->counts[idx]++; return; } idx = (idx + 1) % map->capacity; if (idx == start) return; } map->keys[idx] = key; map->counts[idx] = 1; map->occupied[idx] = 1; } int getCount(HashMap *map, int key) { int idx = hashFunc(key, map->capacity); int start = idx; while (map->occupied[idx]) { if (map->keys[idx] == key) return map->counts[idx]; idx = (idx + 1) % map->capacity; if (idx == start) break; } return 0; } int findUniqueHash(const int arr[], int n) { if (n <= 0) return -1; HashMap *map = createHashMap(n * 2 + 1); if (map == NULL) return -1; for (int i = 0; i < n; i++) { increment(map, arr[i]); } int result = -1; for (int i = 0; i < n; i++) { if (getCount(map, arr[i]) == 1) { result = arr[i]; break; } } freeHashMap(map); return result; } /* XOR: O(n) time, O(1) space */ int findUniqueXOR(const int arr[], int n) { int result = 0; for (int i = 0; i < n; i++) { result ^= arr[i]; } return result; } /* 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[] = {2, 3, 5, 4, 5, 3, 4}; int n1 = sizeof(arr1) / sizeof(arr1[0]); printf("\nArray 1: "); printArray(arr1, n1); printf("Naive: %d\n", findUniqueNaive(arr1, n1)); printf("Hash: %d\n", findUniqueHash(arr1, n1)); printf("XOR: %d\n", findUniqueXOR(arr1, n1)); int arr2[] = {2, 2, 5, 5, 20, 30, 30}; int n2 = sizeof(arr2) / sizeof(arr2[0]); printf("\nArray 2: "); printArray(arr2, n2); printf("Naive: %d\n", findUniqueNaive(arr2, n2)); printf("Hash: %d\n", findUniqueHash(arr2, n2)); printf("XOR: %d\n", findUniqueXOR(arr2, n2)); int arr3[] = {7}; int n3 = sizeof(arr3) / sizeof(arr3[0]); printf("\nArray 3 (single): "); printArray(arr3, n3); printf("XOR: %d\n", findUniqueXOR(arr3, n3)); int arr4[] = {-1, -2, -1, -3, -2}; int n4 = sizeof(arr4) / sizeof(arr4[0]); printf("\nArray 4 (negatives): "); printArray(arr4, n4); printf("XOR: %d\n", findUniqueXOR(arr4, n4)); } /* Performance comparison */ void performanceComparison(void) { printf("\n=== Performance Comparison (n = 100001) ===\n"); int n = 100001; int *arr = malloc(n * sizeof(int)); if (arr == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return; } /* Fill pairs + one unique */ for (int i = 0; i < n / 2; i++) { arr[2 * i] = i + 1; arr[2 * i + 1] = i + 1; } arr[n - 1] = 999999; /* Unique element */ clock_t start, end; double timeTaken; /* Hash */ start = clock(); int hashResult = findUniqueHash(arr, n); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Hash (O(n)): Result = %d, Time = %.3f ms\n", hashResult, timeTaken); /* XOR */ start = clock(); int xorResult = findUniqueXOR(arr, n); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("XOR (O(n)): Result = %d, Time = %.3f ms\n", xorResult, timeTaken); printf("\nVerification: %s\n", (hashResult == xorResult) ? "PASS" : "FAIL"); free(arr); } /* Demonstrates edge cases */ void demonstrateEdgeCases(void) { printf("\n=== Edge Cases ===\n"); /* Case 1: Single element */ int arr1[] = {42}; printf("Case 1: Single element\n"); printf(" Array: "); printArray(arr1, 1); printf(" Unique: %d\n", findUniqueXOR(arr1, 1)); /* Case 2: Unique at start */ int arr2[] = {99, 1, 1, 2, 2}; printf("\nCase 2: Unique at start\n"); printf(" Array: "); printArray(arr2, 5); printf(" Unique: %d\n", findUniqueXOR(arr2, 5)); /* Case 3: Unique at end */ int arr3[] = {1, 1, 2, 2, 99}; printf("\nCase 3: Unique at end\n"); printf(" Array: "); printArray(arr3, 5); printf(" Unique: %d\n", findUniqueXOR(arr3, 5)); /* Case 4: Negative unique */ int arr4[] = {-5, -5, -10, -3, -3}; printf("\nCase 4: Negative unique\n"); printf(" Array: "); printArray(arr4, 5); printf(" Unique: %d\n", findUniqueXOR(arr4, 5)); /* Case 5: Zero unique */ int arr5[] = {1, 1, 0, 2, 2}; printf("\nCase 5: Zero unique\n"); printf(" Array: "); printArray(arr5, 5); printf(" Unique: %d\n", findUniqueXOR(arr5, 5)); /* Case 6: Large unique value */ int arr6[] = {1, 1, 2147483647, 2, 2}; printf("\nCase 6: Large unique value\n"); printf(" Array: "); printArray(arr6, 5); printf(" Unique: %d\n", findUniqueXOR(arr6, 5)); /* Case 7: All pairs, no unique (invalid input) */ int arr7[] = {1, 1, 2, 2}; printf("\nCase 7: Invalid input (all pairs)\n"); printf(" Array: "); printArray(arr7, 4); printf(" XOR result: %d (no unique exists)\n", findUniqueXOR(arr7, 4)); } /* 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: Counts occurrences with nested loops; O(n²).
2. Hash: Uses a hash table to count frequencies; O(n) average.
3. XOR: XORs all elements; pairs cancel leaving the unique; O(n), O(1) space.

Expected Output (sample run)

text

=== Unique 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: [2, 3, 5, 4, 5, 3, 4] Naive: 2 Hash: 2 XOR: 2 Array 2: [2, 2, 5, 5, 20, 30, 30] Naive: 20 Hash: 20 XOR: 20 Array 3 (single): [7] XOR: 7 Array 4 (negatives): [-1, -2, -1, -3, -2] XOR: -3 --- Menu --- ... Enter choice: 3 === Performance Comparison (n = 100001) === Hash (O(n)): Result = 999999, Time = 18.456 ms XOR (O(n)): Result = 999999, Time = 0.312 ms Verification: PASS --- Menu --- ... Enter choice: 4 === Edge Cases === Case 1: Single element Array: [42] Unique: 42 Case 2: Unique at start Array: [99, 1, 1, 2, 2] Unique: 99 Case 3: Unique at end Array: [1, 1, 2, 2, 99] Unique: 99 Case 4: Negative unique Array: [-5, -5, -10, -3, -3] Unique: -10 Case 5: Zero unique Array: [1, 1, 0, 2, 2] Unique: 0 Case 6: Large unique value Array: [1, 1, 2147483647, 2, 2] Unique: 2147483647 Case 7: Invalid input (all pairs) Array: [1, 1, 2, 2] XOR result: 0 (no unique exists)

---

Common Pitfalls, Edge Cases & Memory Considerations

1. Assumption of Exactly One Unique

XOR returns 0 if all elements are paired (no unique). The problem guarantees exactly one unique.

2. Empty Array

XOR returns 0 for empty arrays, which may be misinterpreted as a valid unique value.

c

if (n <= 0) return -1; /* Handle explicitly */

3. Integer Overflow

XOR does not overflow; it operates bit-by-bit.

4. Negative Values

XOR works correctly with negative numbers (two’s complement).

c

int arr[] = {-1, -2, -1, -3, -2}; /* XOR = -3 */

5. Hash Table Sizing

Hash table should be sized ≥ 2× array size for good performance.

c

createHashMap(n * 2 + 1);

6. Hash Table Overflow

If the table fills up, insertions silently fail.

Solution: Size the table generously (2× or more).

7. Using unordered_map in C++

C does not have built-in hash maps; you must implement or use uthash.

Solution: Use XOR when possible (simplest and fastest).

8. Memory Leaks

Free hash table memory after use.

c

freeHashMap(map);

9. Large Unique Value

Unique value can be any int; use int not unsigned.

10. Memory Considerations

• Naive: O(1) extra space.
• Hash: O(n) extra space.
• XOR: O(1) extra space — preferred.
• XOR is the most efficient and simplest approach.

---

Summary & Best Practices

Finding the unique element where all others appear twice is elegantly solved using XOR. The XOR of all elements cancels pairs, leaving only the unique element.

Key Takeaways

• XOR cancels identical pairs: a ⊕ a = 0.
• XOR identity: a ⊕ 0 = a.
• XOR all elements → unique element.
• Naive: O(n²) time, O(1) space.
• Hash: O(n) time, O(n) space.
• XOR: O(n) time, O(1) space — optimal.
• Problem guarantees exactly one unique element.

Best Practices

1. Use XOR for O(n) time and O(1) space.
2. Verify the problem’s guarantee (exactly one unique).
3. Handle empty arrays explicitly.
4. Test with negative values and zeros.
5. Use hash map only when XOR isn’t applicable (e.g., unique appears 3 times).
6. Free hash map memory after use.
7. Size hash tables generously for good performance.
8. Use int (signed) for the result.
9. Document the XOR property in comments.
10. Profile for large arrays.

By mastering this problem, you’ll understand the power of XOR and be prepared for related bitwise problems like Single Number II and III.