Single Number in an Array

Finding the single number in an array is one of the most popular coding problems frequently encountered in technical interviews and algorithm challenges. The task is to identify the unique element in an array where every other number appears twice. This problem is a great way to test your understanding of array manipulation, bitwise operations, and time complexity optimization. Whether you're preparing for coding interviews or just looking to enhance your problem-solving skills, mastering how to find the single number in an array.

In this guide, we’ll cover the most efficient methods, including XOR operation, hash maps, and sorting algorithms, to help you solve the problem with ease and precision.

Steps to Solve the "Single Number in an Array" Problem:

• Understand the Problem:
  • The input is an array where every element appears twice except for one unique number.
  • Your task is to find that unique number.
• XOR Approach (Optimal):
  • Use the XOR operator to find the unique number.
  • XOR of two same numbers results in 0, and XOR of any number with 0 results in the number itself.
  • XOR all elements in the array; duplicates will cancel each other out, leaving only the unique number.
  • Time Complexity: O(n), Space Complexity: O(1).
• Hash Map Approach:
  • Traverse the array and store the count of each element in a hash map.
  • The element that appears only once is the required result.
  • Time Complexity: O(n), Space Complexity: O(n).
• Sorting Approach:
  • Sort the array first and then iterate through it to check for adjacent duplicate elements.
  • The element that does not have a duplicate adjacent to it is the unique number.
  • Time Complexity: O(n log n), Space Complexity: O(1) if sorting in-place.
• Edge Case Considerations:
  • Handle the case where the array contains only one element.
  • Ensure that the solution works for arrays with negative and large numbers.

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.