Finding the Single Number in an Array Using XOR in PHP

When solving coding problems, especially those related to arrays, we often encounter the need to find a unique element while all others appear twice. One effective way to achieve this is by using bitwise XOR operations. In this post, I'll walk through a solution to find a single number in an array using XOR in PHP.

Problem Statement

You are given a non-empty array of integers where every element appears twice, except for one. Your task is to find that single number.

The XOR Trick

Bitwise XOR (denoted as ^ in PHP) has some useful properties:

a ^ a = 0 (any number XORed with itself results in 0)

a ^ 0 = a (any number XORed with 0 remains unchanged)

XOR is both commutative and associative, which means the order of operations doesn’t matter. Using these properties, we can reduce this problem to a single pass over the array, XORing all the elements. The numbers that appear in pairs will cancel each other out, leaving us with the single number.

PHP Implementation

Here’s how you can implement this solution:

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function singleNumber($nums) {
        $result = 0;

        // XOR all the elements
        foreach ($nums as $num) {
            $result ^= $num;
        }

        return $result;
    }
}

How It Works

  1. We initialize the result to 0.
  2. We iterate through each number in the array.
  3. We XOR each number with the result.
  4. By the end of the loop, all paired numbers will have canceled out, and we are left with the single number.

Example

Let’s see how the algorithm works with an example:

Input: [2, 1, 4, 2, 1]

Steps:

  • Initial result = 0
  • XOR with 2: 0 ^ 2 = 2
  • XOR with 1: 2 ^ 1 = 3
  • XOR with 4: 3 ^ 4 = 7
  • XOR with 2: 7 ^ 2 = 5
  • XOR with 1: 5 ^ 1 = 4

Final result: 4

Time Complexity

The time complexity of this solution is O(n), where n is the number of elements in the array. This is because we make a single pass through the array.

Conclusion

This bitwise XOR approach is not only simple but also highly efficient, making it a great solution to problems where we need to find a unique number in an array where all other numbers appear in pairs.