NUHMAN.com

Introduction

LeetCode 136: Single Number is a classic problem that asks you to find the element in an array that appears only once, while all other elements appear exactly twice. The challenge is to find an efficient solution that minimizes both time and space complexity.

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 time complexity of O(n) and constant extra space.

Example:

go

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

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

Explanation:

In the first example, the number 1 is the only number that appears once, while 2 appears twice. Similarly, in the second example, the number 4 is the only number that appears once.

Approach:

XOR Approach:

The most efficient way to solve this problem is to use the XOR (exclusive OR) operation. XOR has some unique properties that make it a perfect fit for this problem:

1. Property 1: a ^ a = 0 (XOR of a number with itself is 0).
2. Property 2: a ^ 0 = a (XOR of a number with 0 is the number itself).
3. Property 3: XOR is commutative and associative, meaning the order of operations doesn’t matter. For example, a ^ b ^ c = c ^ a ^ b.

By applying XOR across all the numbers in the array, the numbers that appear twice will cancel each other out (because of Property 1), leaving only the number that appears once.

Steps:

1. Initialize a variable result with 0.
2. Traverse through the array, applying XOR between the result and each element.
3. At the end of the loop, result will hold the single number that appears only once.

This approach runs in O(n) time complexity because we only need to traverse the array once, and it uses O(1) space since we only use a single variable (result) for the XOR operation.

Go Implementation

Solution Using XOR

go

package main

import "fmt"

func singleNumber(nums []int) int {
    result := 0
    for _, num := range nums {
        result ^= num // Apply XOR for each number
    }
    return result
}

func main() {
    // Test the function with example cases
    nums1 := []int{2, 2, 1}
    nums2 := []int{4, 1, 2, 1, 2}

    fmt.Println("Single Number in nums1:", singleNumber(nums1)) // Output: 1
    fmt.Println("Single Number in nums2:", singleNumber(nums2)) // Output: 4
}

Explanation:

1. singleNumber Function:

• We initialize result to 0.
• Loop through the nums array, applying XOR to each element with the current value of result.
• After all elements are processed, the result holds the number that appears only once.

1. main Function:

• In the main function, we test the singleNumber function with two example inputs (nums1 and nums2).
• The function correctly returns the single number from the array.

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(1)

Time Complexity:

• O(n) because we traverse the entire array once to apply XOR on each element, where n is the number of elements in the array.

Space Complexity:

• O(1) because we only use a single variable (result) to store the intermediate XOR result. No additional space is required.

Edge Cases

1. Single Element:

• Input: nums = [1]
• Output: 1
• Explanation: If the array contains only one element, that element is the answer since it is the only one that appears.

1. Array with Multiple Duplicates:

• Input: nums = [3, 5, 5, 3, 2]
• Output: 2
• Explanation: The numbers 3 and 5 appear twice, leaving 2 as the single number.

1. Array with Negative Numbers:

• Input: nums = [-1, -2, -2, -1, -3]
• Output: -3
• Explanation: In this case, -1 and -2 appear twice, and -3 is the single number.

Conclusion

LeetCode 136: Single Number is a great problem to practice bitwise operations, especially XOR. The XOR approach provides an efficient solution with O(n) time complexity and O(1) space complexity. This approach leverages the unique properties of XOR to eliminate pairs of duplicate elements and isolate the element that appears only once.