LeetCode: Single Number — Optimal Solution Explained

LeetCode: Single Number — Optimal Solution Explained

Table of Content

• Introduction
• Intuition/Solution
• Step-by-Step Visual Guide
• Implementation Code

Introduction

Finding the unique element in an array, where every element appears twice, except for one. This is the intriguing premise of the “Single Number” problem on LeetCode.

While there are various ways to approach this problem, today, we will explore a clever bitwise solution using the XOR operation.

We will guide you step by step, using clear visuals to demonstrate how the solution works with time complexity of O(n) and space complexity of O(1)

Intuition/Solution

At first glance, it might be tempting to use data structures like sets or dictionaries to keep track of the elements and their counts. However, these approaches require extra memory. The challenge lies in finding a linear-time solution that doesn’t rely on additional memory allocation.

In programming, XOR (exclusive OR) is a bitwise operation that compares two binary numbers bit by bit. For each pair of corresponding bits, the XOR operation outputs 1 if the bits are different, and 0 if the bits are the same. In other words, it returns true if only one of the input bits is true (1) and false (0) otherwise.

Input A | Input B | Output (A XOR B)
-------------------------------------
   0    |    0    |        0
   0    |    1    |        1
   1    |    0    |        1
   1    |    1    |        0

Here are two key properties of XOR that make it unique and useful in problem-solving:

1. A number XORed with itself results in 0 (A XOR A = 0).

101
XOR
101
-----
000

2. A number XORed with 0 results in the same number (A XOR 0 = A).

Here’s an example

111
XOR
000
-----
111

These properties allow XOR to be used as a tool to cancel out duplicates and isolate unique elements in a set of numbers, making it a powerful operation for solving various programming problems.

Here’s a step-by-step breakdown of the solution:

1. Initialize a variable, say single_number, with 0.
2. Iterate through the array and XOR each element with the single_number variable. This will effectively cancel out the duplicate elements and store the unique number in the variable.
3. After iterating through the entire array, the single_number variable will hold the single unique number.

Step-by-Step Visual Guide

Example

Let’s go through the “Single Number” problem solution visually and in binary using the example: [4, 1, 2, 1, 2].

1. Initialize a variable single_number with the value 0:

single_number = 0 (in binary: 0000)

2. Iterate through the array and XOR each element with the single_number variable:

Array: [4, 1, 2, 1, 2]

XOR operations (in decimal and binary):

1st iteration:
single_number = single_number ^ 4
single_number = 0 ^ 4
single_number = 4
Binary: 0000 ^ 0100 = 0100

2nd iteration:
single_number = single_number ^ 1
single_number = 4 ^ 1
single_number = 5
Binary: 0100 ^ 0001 = 0101

3rd iteration:
single_number = single_number ^ 2
single_number = 5 ^ 2
single_number = 7
Binary: 0101 ^ 0010 = 0111

4th iteration:
single_number = single_number ^ 1
single_number = 7 ^ 1
single_number = 6
Binary: 0111 ^ 0001 = 0110

5th iteration:
single_number = single_number ^ 2
single_number = 6 ^ 2
single_number = 4
Binary: 0110 ^ 0010 = 0100

3. After iterating through the entire array, the single_number variable holds the unique number (4 in this case):

single_number = 4 (in binary: 0100)

By applying the XOR operation on all elements of the array and using the properties of XOR, the duplicate elements cancel each other out, leaving us with the single unique number.

Implementation Code

Python

def singleNumber(nums):
    single_number = 0
    for num in nums:
        single_number ^= num
    return single_number

Javascript

function singleNumber(nums) {
    let single_number = 0;
    for (let num of nums) {
        single_number ^= num;
    }
    return single_number;
}