Missing Number
EasyThe problem
nums holds n different numbers taken from 0 to n. Exactly one number in that range is missing. Return it.
- Example 1Input: nums = [3, 0, 1]Output: 2
n = 3, so the range is 0 to 3, and 2 is not there.
- Example 2Input: nums = [0, 1]Output: 2
The range is 0 to 2.
- Example 3Input: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]Output: 8
Limits
- 1 ≤ n = len(nums) ≤ 10,000
- All numbers in nums are different and between 0 and n
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
Numbers 0..n appear once except one. Which operation cancels equal values?
The idea
XOR all indices 0..n with all values (or sum formula n(n+1)/2 minus the array sum).
Target: O(n) time, O(1) space
Go function shape
func missingNumber(nums []int) intReference 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
}