Find Single Number (XOR Trick) in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include <stdio.h>

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

int main() {
    int arr[] = {2, 1, 4, 5, 2, 4, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("The single number is %d\n", findSingle(arr, n));
    return 0;
}

C Output

The single number is 5

C++ Program

#include <iostream>
using namespace std;

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

int main() {
    int arr[] = {7, 3, 5, 3, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The single number is " << findSingle(arr, n) << endl;
    return 0;
}

C++ Output

The single number is 7

JAVA Program

public class Main {
    static int findSingle(int[] arr, int n) {
        if (n == 1) return arr[0];
        return arr[0] ^ findSingle(sliceArray(arr, 1, n), n - 1);
    }

    static int[] sliceArray(int[] arr, int start, int end) {
        int[] result = new int[end - start];
        for (int i = start; i < end; i++) {
            result[i - start] = arr[i];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {10, 14, 10, 14, 99};
        System.out.println("The single number is " + findSingle(arr, arr.length));
    }
}

JAVA Output

The single number is 99

Python Program

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

arr = [6, 1, 2, 1, 2]
n = len(arr)
print("The single number is", find_single(arr, n))

Python Output

The single number is 6

Explanation

Example

Consider the array [2, 1, 4, 5, 2, 4, 1]. When we perform XOR operation on all the numbers:

2 ^ 1 ^ 4 ^ 5 ^ 2 ^ 4 ^ 1 → pairs such as (2 ^ 2) reduce to 0 and (1 ^ 1) reduce to 0, leaving only 5. This is due to the property x ^ x = 0 and x ^ 0 = x. The sequence does not matter, so XORing them in any order gives the same answer.

Real-Life Analogy

Try imagining a pile of socks in a laundry basket. Each sock has the same partner except for one. If you continue to remove pairs, after a while, only the stray sock will be left. XOR does the same thing — it removes matching numbers and leaves the sole survivor.

Why It Matters

This method is perhaps one of the neatest and most efficient solutions to a problem that would otherwise have to be done in additional memory. Typically, you'd probably do frequency counting using a hash map, which costs O(n) space. Using XOR, you achieve the solution in O(1) additional space and O(n) time.

Learning Insights

This exercise illustrates the way in which counting-based logic can be replaced with bitwise operation. It illustrates that mathematical properties can result in very simplistic solutions at times. For junior programmers, this is a precursor to more complex bit manipulation tricks applied in encryption, compression, and error detection.

Interview and Real-World Usage

In interviews, "Find the single number" is a favorite because it will challenge your understanding of XOR and your pattern recognition skills for problems. In the real world, XOR is applied in networking protocols for calculating checksums, in cryptography for easy encryption, and in hardware design for parity checks.

SEO-Friendly Closing

Finding the single number using the XOR trick is a time-honored programming exercise done well with bitwise tricks. The technique is used in C, C++, Java, and Python without additional space, and it's a favorite in coding interviews and competitive programming. Knowing how XOR eliminates duplicate values impresses programmers with the power of bitwise logic, an ability useful in algorithms, data processing, and system programming.