Find Element Occurring Odd Number of Times in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include <stdio.h>

int findOdd(int arr[], int n) {
    if (n == 1) return arr[0];
    return arr[0] ^ findOdd(arr + 1, n - 1);
}

int main() {
    int arr[] = {2, 3, 2, 3, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("The element occurring odd number of times is %d\n", findOdd(arr, n));
    return 0;
}

C Output

The element occurring odd number of times is 5

C++ Program

#include <iostream>
using namespace std;

int findOdd(int arr[], int n) {
    if (n == 1) return arr[0];
    return arr[0] ^ findOdd(arr + 1, n - 1);
}

int main() {
    int arr[] = {1, 2, 3, 2, 3, 1, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The element occurring odd number of times is " << findOdd(arr, n) << endl;
    return 0;
}

C++ Output

The element occurring odd number of times is 3

JAVA Program

import java.util.*;

class L {
    public static void main(String[] a) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), x = sc.nextInt(), i;
        int[] arr = new int[n];
        for(i = 0; i < n; i++) arr[i] = sc.nextInt();
        for(i = 0; i < n && arr[i] != x; i++);
        System.out.print(i < n ? "Found at " + i : "Not Found");
    }
}

JAVA Output

The element occurring odd number of times is 3

Python Program

def find_odd(arr, n):
    if n == 1:
        return arr[0]
    return arr[0] ^ find_odd(arr[1:], n - 1)

arr = [2, 2, 3, 3, 4]
n = len(arr)
print("The element occurring odd number of times is", find_odd(arr, n))

Python Output

The element occurring odd number of times is 4

Explanation

Example

Consider an array [2, 3, 2, 3, 5]. Every number that appears an even number of times will cancel itself out when XOR-ed together. That means 2 ^ 2 = 0 and 3 ^ 3 = 0, leaving 0 ^ 5 = 5 as the result. This is precisely the way our recursive solution functions — it continues to merge elements by XOR until only one number is left, which is the number that occurs an odd number of times. 

Real-Life Analogy

Suppose you are in a room where each person has a twin, but one single person doesn't have a twin. If all the people pair up and exit the room, the single person without a twin remains behind. XOR is like this pairing scheme: equal numbers wipe each other out, and the odd one remains at the end.

Why It Matters

This exercise preaches the application of bitwise XOR in a practical context. XOR is such a strong function as it possesses distinctive mathematical properties — x ^ x = 0 and x ^ 0 = x. These properties are used in many competitive programming problems as well as in interview questions to solve problems quickly without additional memory.

Learning Insights

Applying recursion here makes the answer elegant and beautiful. It supports the notion that recursion can be applied to array slices, making the problem smaller at each step. This specific problem also shows how we might tackle some algorithmic problems without direct counting or hashing — solely mathematical operations.

Use in Interviews and Projects

In interviews, it is a traditional "bit manipulation" question. Interviewers usually provide an extension where there are many odd-occurring elements or larger limits to check the optimization ability. In actual projects, XOR-based methods are applied to error detection algorithms, data encoding, and checksum calculation due to the lightweight and fast nature.

SEO-Friendly Closing

Identification of an element appearing an odd number of times with recursion in C, C++, Java, and Python is another classic example of using recursion alongside bitwise operations to efficiently solve a problem. It is commonly utilized during coding interviews and competitive programming since it takes linear time and constant space, making it both efficient and space-friendly. Realizing this method not only enhances recursion ability but also gains a good understanding in bitwise manipulation, which can be applied extensively in algorithms, security, and data handling.