Single Number

Easy

The problem

In nums every number appears exactly twice, except for one number that appears only once. Return that number.

Example 1
Input: nums = [2, 2, 1]
Output: 1
Example 2
Input: nums = [4, 1, 2, 1, 2]
Output: 4
1 and 2 each appear twice. 4 appears once.

Limits

1 ≤ len(nums) ≤ 30,000
Exactly one number appears once, all others twice
Aim for no extra memory that grows with the input

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

What is x XOR x? What is x XOR 0?

The idea

XOR all numbers: pairs cancel, the single number remains.

Target: O(n) time, O(1) space

Go function shape

func singleNumber(nums []int) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// SingleNumber: every value appears twice except one.
// x ^ x == 0 and x ^ 0 == x, so XOR-ing everything cancels the pairs.
func SingleNumber(nums []int) int {
	result := 0
	for _, n := range nums {
		result ^= n
	}
	return result
}

// MissingNumber: XOR every index and every value; only the missing number is left unpaired.
func MissingNumber(nums []int) int {
	result := len(nums)
	for i, n := range nums {
		result ^= i ^ n
	}
	return result
}

Read the lesson: Bit Manipulation & Math