136. Single Number

Problem Statement

link: https://leetcode.com/problems/single-number/ https://leetcode.cn/problems/single-number/

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:

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

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

Input: nums = [1] Output: 1

Solution Approach

Use bit manipulation or mathematical properties to isolate the single number from pairs in the array.

Algorithm

1. Bit Manipulation (Using XOR): XOR all numbers; identical numbers cancel each other, leaving the single number as the result.
2. Mathematical Approach: Double the sum of unique numbers, then subtract the sum of the entire array to find the single number.
3. The provided code showcases both the XOR and mathematical methods.

Implement

    class Solution:
  def singleNumber(self, nums: List[int]) -> int:
      return reduce(lambda x, y: x ^ y, nums)
      
class Solution:
  def singleNumber(self, nums: List[int]) -> int:
      singleNos = set(nums)
      return sum(singleNos) * 2 - sum(nums)    
 

    
    

Twitter  facebook  Email