C Program to Find Odd Occurring Number

You can find the odd occurring number in C by using the XOR operator in a loop like for (int i = 0; i < n; i++) result ^= arr[i]; which gives the number that appears an odd number of times.

Examples

Inputarr = {1, 2, 3, 2, 3, 1, 3}

Output3

Inputarr = {4, 4, 5, 5, 5}

Output5

Inputarr = {7}

Output7

How to Think About It

To find the number that appears an odd number of times, use the XOR operator because XOR of a number with itself is 0 and XOR with 0 is the number itself. So, XORing all numbers cancels out even occurrences and leaves the odd occurring number.

Algorithm

1

Initialize a variable result to 0.

2

Loop through each element in the array.

3

XOR the current element with result and store back in result.

4

After the loop ends, result holds the odd occurring number.

5

Return or print the result.

Code

c

#include <stdio.h>

int findOdd(int arr[], int n) {
    int result = 0;
    for (int i = 0; i < n; i++) {
        result ^= arr[i];
    }
    return result;
}

int main() {
    int arr[] = {1, 2, 3, 2, 3, 1, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Odd occurring number is %d\n", findOdd(arr, n));
    return 0;
}

Output

Odd occurring number is 3

Dry Run

Let's trace the array {1, 2, 3, 2, 3, 1, 3} through the code

1

Initialize result

result = 0

2

XOR with 1

result = 0 ^ 1 = 1

3

XOR with 2

result = 1 ^ 2 = 3

4

XOR with 3

result = 3 ^ 3 = 0

5

XOR with 2

result = 0 ^ 2 = 2

6

XOR with 3

result = 2 ^ 3 = 1

7

XOR with 1

result = 1 ^ 1 = 0

8

XOR with 3

result = 0 ^ 3 = 3

Iteration	Current Element	Result after XOR
1	1	1
2	2	3
3	3	0
4	2	2
5	3	1
6	1	0
7	3	3

Why This Works

Step 1: XOR cancels pairs

XOR of a number with itself is 0, so pairs of the same number cancel out.

Step 2: XOR with zero

XOR of any number with 0 is the number itself, so starting with 0 keeps the first number.

Step 3: Result is odd occurring number

After XORing all elements, only the number occurring odd times remains in result.

Alternative Approaches

Using Hash Map

c

#include <stdio.h>
#include <stdlib.h>

int findOdd(int arr[], int n) {
    int freq[1000] = {0};
    for (int i = 0; i < n; i++) {
        freq[arr[i]]++;
    }
    for (int i = 0; i < 1000; i++) {
        if (freq[i] % 2 != 0) {
            return i;
        }
    }
    return -1;
}

int main() {
    int arr[] = {1, 2, 3, 2, 3, 1, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Odd occurring number is %d\n", findOdd(arr, n));
    return 0;
}

Uses extra space for frequency array; simpler but less efficient.

Brute Force Counting

c

#include <stdio.h>

int findOdd(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 % 2 != 0) return arr[i];
    }
    return -1;
}

int main() {
    int arr[] = {1, 2, 3, 2, 3, 1, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Odd occurring number is %d\n", findOdd(arr, n));
    return 0;
}

Simple but slow; time complexity is O(n²).

Complexity: O(n) time, O(1) space

Time Complexity

The program loops through the array once, so time is O(n), where n is the number of elements.

Space Complexity

Only one variable is used to store the XOR result, so space is O(1).

Which Approach is Fastest?

The XOR method is fastest and uses least memory compared to hash map or brute force.

Approach	Time	Space	Best For
XOR Method	O(n)	O(1)	Large arrays, memory efficient
Hash Map	O(n)	O(n)	When numbers are large or not suitable for XOR
Brute Force	O(n²)	O(1)	Small arrays or simple logic