Finding the Single Number in an Array

Have you ever felt like the odd one out in a crowd? Imagine being at a party where everyone is in pairs, but you’re the only one without a partner. You stand out, right? In programming, sometimes we need to find that one "odd" number in a list where every other number appears in pairs. It’s like finding that one person at the party who doesn’t have a match.

Let me share a quick story about Albert Einstein. As a child, Einstein was different from other kids. He spoke late, had unique thoughts, and didn’t fit into the standard mold. But being different is what made him special. Similarly, in an array where every number appears twice, there’s one unique number that stands out. Our job is to find that "single" number.

So, how do we find this single number in an array? Let’s explore this interesting problem step by step.

Problem statement

You’re given an array of integers. Every element in the array appears twice, except for one element which appears only once. Your task is to find and return that single number.

Sample input

1[2, 3, 5, 4, 5, 3, 2]

Sample output

14

Explanation:
In this example, every number except 4 appears twice. The number 4 is the single number that does not have a pair, so it’s our answer.

Understanding the problem

At first glance, this problem might seem simple, but it requires careful thinking. Imagine you’re at a fair with lots of identical pairs of toys. There’s only one toy that’s different, and you need to find it. You wouldn’t want to go through each toy multiple times, right? Similarly, we need to find an efficient way to identify the single number in our array.

Brute force approach

The simplest way to find the single number is to compare each element with every other element. If it doesn’t have a match, then it’s the single number. However, this approach can be slow and time-consuming, especially for large arrays.

Pseudocode

Let’s break down the solution into simple steps that even beginners can follow. Here’s the pseudocode in plain English:

• Initialize a variable result to 0.
• For each number in the array:
  • XOR the number with result.
  • Store the result back into result.
• After going through all numbers, result will hold the single number.

This pseudocode captures the essence of the problem and outlines a clear path to the solution.

Python code

Let’s start with the most straightforward approach, where we manually check each element.

1def find_single_number(arr):
2    for num in arr:
3        if arr.count(num) == 1:
4            return num

Explanation

• We loop through each element in the array.
• The count() function checks how many times each number appears.
• If a number appears only once, we return it as the single number.

Java code

1public class SingleNumber {
2    public static int findSingleNumber(int[] arr) {
3        for (int num : arr) {
4            int count = 0;
5            for (int element : arr) {
6                if (element == num) {
7                    count++;
8                }
9            }
10            if (count == 1) {
11                return num;
12            }
13        }
14        return -1; // If no single number found
15    }
16}

C++ code

1#include <vector>
2
3int findSingleNumber(const std::vector<int>& arr) {
4    for (int num : arr) {
5        int count = 0;
6        for (int element : arr) {
7            if (element == num) {
8                count++;
9            }
10        }
11        if (count == 1) {
12            return num;
13        }
14    }
15    return -1; // If no single number found
16}

Explanation

• The brute force approach checks every element against all others.
• It counts how many times each number appears.
• The time complexity is O(n^2) because of the nested loops, making it inefficient for large arrays.

A smarter approach

A more efficient way is to use mathematical operations like XOR (exclusive OR). XOR has a special property: when you XOR two identical numbers, the result is 0. So, if you XOR all the numbers in the array together, the pairs will cancel each other out, leaving you with the single number.

Efficient approach using XOR

Now, let’s improve the solution using the XOR operation, which is more efficient.

Python code

1def find_single_number(arr):
2    result = 0
3    for num in arr:
4        result ^= num
5    return result

Explanation

• We initialize result to 0.
• We then XOR each number with result. Because XOR of a number with itself is 0, all pairs will cancel out, leaving the single number.
• The time complexity is O(n), making it much faster than the brute force approach.

Java code

1public class SingleNumber {
2    public static int findSingleNumber(int[] arr) {
3        int result = 0;
4        for (int num : arr) {
5            result ^= num;
6        }
7        return result;
8    }
9}

C++ code

1#include <vector>
2
3int findSingleNumber(const std::vector<int>& arr) {
4    int result = 0;
5    for (int num : arr) {
6        result ^= num;
7    }
8    return result;
9}

Explanation

• The logic is identical across Python, Java, and C++.
• XOR is used to cancel out all duplicate numbers, leaving only the single number.
• This approach is optimal, both in terms of time and space.

Conclusion

Finding the single number in an array is like finding that one person at a party who doesn’t have a match. While the brute force approach can solve the problem, it’s not efficient for large arrays. The XOR method, on the other hand, offers a smart and efficient solution that works quickly, even with large datasets.

Just like Albert Einstein stood out because he was different, the single number in an array stands out because it doesn’t have a pair. By understanding and applying these methods, you not only solve this specific problem but also gain insights into how to approach and solve similar problems in programming.