Embedded Prep

Master the problem of finding the number that appears odd number of times in an array with this beginner-friendly guide. Learn step-by-step how the XOR operation works to solve this problem efficiently in O(n) time and O(1) space. Includes detailed explanations, example walkthroughs, and fully working code in C, C++, Java, and Python. Perfect for coding interview preparation, competitive programming, and improving problem-solving skills.

In coding interviews and competitive programming, a popular problem is:

Find the Number That Appears Odd Number of Times

It’s a simple question, but there’s a clever trick to solve it efficiently. This article will explain the problem in depth, walk you through the logic step-by-step, and provide solutions in C, C++, Java, and Python.

Problem Statement

Given an array of integers, all numbers occur an even number of times except one. Your task is to find that number.

Example:

Input:  arr = [2, 3, 2, 3, 4]
Output: 4
Explanation: 2 appears twice, 3 appears twice, and 4 appears once (odd number of times).

Naive Approach – Count Frequency

A beginner might think:

1. Loop through the array.
2. Count how many times each number occurs.
3. Return the number with an odd count.

Problem:

• Time Complexity → O(n²) (if we count for each number)
• Not efficient for large datasets.

Naive Solution

int findOdd(int arr[], int n) {
// Outer loop: pick each element one by one
for (int i = 0; i < n; i++) {
int count = 0; // reset count for the current element
// Inner loop: compare the picked element with every element
    for (int j = 0; j < n; j++) {
        if (arr[i] == arr[j]) { // if both are same
            count++; // increase occurrence count
        }
    }

    // If the count is odd, return this number
    if (count % 2 != 0) {
        return arr[i];
    }
}
return -1; // if no odd occurrence found
}

How it works:

1. Outer loop (i) → Selects each number in the array one by one.
2. Inner loop (j) → Compares that number with all elements in the array.
3. count++ → Every time it matches, we increase the counter.
4. After the inner loop ends, we check:

if (count % 2 != 0)

If count is odd, that’s our answer.

Efficient Approach – Using XOR

The XOR ( ^ ) bitwise operator has special properties:

• x ^ x = 0 → a number XORed with itself is 0.
• x ^ 0 = x → a number XORed with 0 stays the same.
• XOR is commutative and associative → order doesn’t matter.

Logic:

• If we XOR all elements in the array, numbers with even occurrences will cancel out to 0.
• The result will be the number that occurs an odd number of times.

Example:

Array: [2, 3, 2, 3, 4]

Step 1: 2 ^ 3 = 1
Step 2: 1 ^ 2 = 3
Step 3: 3 ^ 3 = 0
Step 4: 0 ^ 4 = 4  ✅

Code Examples in Multiple Languages

1️⃣ C Program

#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[] = {2, 3, 2, 3, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Number appearing odd times: %d\n", findOdd(arr, n));
    return 0;
}

2️⃣ C++ Program

#include <iostream>
using namespace std;

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[] = {2, 3, 2, 3, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Number appearing odd times: " << findOdd(arr, n) << endl;
    return 0;
}

3️⃣ Java Program

public class OddOccurrence {
    static int findOdd(int[] arr) {
        int result = 0;
        for (int num : arr) {
            result ^= num;
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 2, 3, 4};
        System.out.println("Number appearing odd times: " + findOdd(arr));
    }
}

4️⃣ Python Program

def find_odd(arr):
    result = 0
    for num in arr:
        result ^= num
    return result

arr = [2, 3, 2, 3, 4]
print("Number appearing odd times:", find_odd(arr))

Key Takeaways

• XOR provides the most efficient solution.
• Time Complexity → O(n)
• Space Complexity → O(1)
• Works across all programming languages with the same logic.
• Very useful in interviews and competitive coding.

🔗 Read More Programming Tutorials: Embedded Prep Master

You can also Visit other tutorials of Embedded Prep 

• Multithreading in C++
• Multithreading Interview Questions
• Multithreading in Operating System
• Multithreading in Java
• POSIX Threads pthread Beginner’s Guide in C/C++
• Speed Up Code using Multithreading
• Limitations of Multithreading
• Common Issues in Multithreading
• Multithreading Program with One Thread for Addition and One for Multiplication
• Advantage of Multithreading
• Disadvantages of Multithreading
• Applications of Multithreading: How Multithreading Makes Modern Software Faster and Smarter”