embeddedprep.com

Category: coding interview question

  • Find the Number That Appears Odd Number of Times | Master Beginner Friendly Tutorials (2026)

    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