Single Number - Python Solution

1. Introduction

The "Single Number" problem is a classic in array manipulation and bitwise operations. It involves finding the unique element in an array where all other elements appear twice. The challenge lies in achieving linear runtime complexity while using only constant extra space, making it a test of efficient algorithm design.

Problem

Given a non-empty array of integers nums, where every element appears twice except for one, the task is to find that single element. The solution must have a linear runtime complexity and use only constant extra space.

2. Solution Steps

1. Realize that XOR-ing a number with itself results in 0 and XOR-ing a number with 0 results in the number itself.

2. Initialize a variable, result, to 0.

3. Iterate through each number in the array.

4. XOR each number with result.

5. Since every number except one appears twice, all such numbers will cancel themselves out, leaving the unique number.

6. Return result, which will hold the single number at the end of the iteration.

3. Code Program

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

# Example Usage
print(singleNumber([2,2,1]))  # Output: 1
print(singleNumber([4,1,2,1,2]))  # Output: 4
print(singleNumber([1]))  # Output: 1

Output:

1
4
1

Explanation:

1. Bitwise XOR: Utilizes the properties of the XOR operation to find the unique element.

2. Canceling Effect: The XOR of a number with itself cancels out to 0, leaving the unique number.

3. Iterative Approach: Iterates through the array, continuously XOR-ing the elements.

4. Constant Space: Uses a single variable for the result, ensuring O(1) space complexity.

5. Linear Time Complexity: The solution runs in O(n) time complexity, where n is the number of elements in the array.

6. Practical Use: Demonstrates a clever use of bitwise operations in array processing.