Single Number - Leetcode Solution

Problem Statement:

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,1] Output: 1

Example 2:

Input: nums = [4,1,2,1,2] Output: 4

Approach:

The given problem can be solved by using the XOR operator.

XOR operator, also known as the exclusive or operator, is a bit-wise operator that takes two binary numbers and performs the logical XOR operation on each pair of corresponding bits. The result of this operation is a binary number where each bit represents whether the corresponding bits of the two operands differ.

XOR can be used to determine which bits are different between two binary numbers. When you XOR two binary numbers, the resulting bits are 1 when the corresponding bits of the two operands differ; otherwise, the resulting bits are 0.

If nums=[2,2,1], as 2^2=0 and 0^1=1, the expression evaluates to 1, which is the required output.

If nums=[4,1,2,1,2], as 4⊕1⊕2⊕1⊕2=(4⊕2)⊕1⊕1⊕2=0⊕2⊕2=0⊕0=0, the expression evaluates to 4 which is the required output.

Algorithm:

1. Initialize a variable called 'output' with 0.
2. Loop through each element in the array.
3. For each element, use the XOR operator to XOR it with the current value of 'output'.
4. Update the value of 'output' with the result of the XOR operation.
5. After looping through all the elements, the final value of 'output' will be the single number that appears only once in the array.

Pseudo Code:

function singleNumber(nums): output = 0 for num in nums: output = output ^ num return output

Complexity Analysis:

Time complexity: O(n). We are looping through each element in the array once.

Space complexity: O(1). We are using only constant extra space.

Code:

class Solution: def singleNumber(self, nums: List[int]) -> int: output = 0 for num in nums: output = output ^ num return output

This solution has been accepted by LeetCode and passes all test cases.

1