# Missing Number

{% embed url="<https://leetcode.com/problems/missing-number/>" %}

## Solution 1

```go
func missingNumber(nums []int) int {
    numsSum, n := 0, len(nums)
    for _,v := range nums {
        numsSum += v
    }
    rangeSum := n*(n+1) / 2
    return rangeSum - numsSum
}
```

The thought process here is easy, compared to solution 2. We are given the `nums` array with one element missing from the range `[0, n]`. Since the numbers are distinct, the difference between the sum of the `nums` array and the sum of all numbers in the range `[0, n]` is actually the missing number.

The rangeSum uses the formula for summing arithmetic sequences:

$$
1+2+\cdots+n = \frac{(1+n)\times n}{2}
$$

## Solution 2

```go
func missingNumber(nums []int) int {
    xor, i := 0, 0
    for ; i < len(nums); i++ {
        xor = xor ^ i ^ nums[i]
    }
    return xor ^ i
}
```

{% hint style="info" %}
Bit manipulation. Note that XOR returns 1 if and only if the bits differ.
{% endhint %}

We use the properties that `X ^ X = 0` and `X ^ 0 = X`. Consider the following example, we have the array `[3, 0, 1]`, `n = 3` in this case, and we are missing 2.&#x20;

The important thing to notice here is that if we have every number in `[0, n]`, then taking the `XOR` results of all the numbers should give us a 0. For this example,

The array `[3, 0, 1, 2]` contains every number in `[0, 3]`, and

```bash
0 ^ 0 ^ 3 ^ 1 ^ 0 ^ 2 ^ 1 ^ 3 ^ 2 = 0    // order doesn't matter
```

For the array with a missing element 2: `[3, 0, 1]`, we have

```bash
0 ^ 0 ^ 3 ^ 1 ^ 0 ^ 2 ^ 1 = 0 ^ 3 ^ 2 = 3 ^ 2
```

The result here is actually 3 (i.e., n) and 2 (the missing element) because the difference between \[0, n-1] and \[0, n] is n and 2 has nothing to cancel itself with. Therefore, taking this result and XOR it with n gives us the final result:

```bash
3 ^ 2 ^ 3 = 2
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blog.yushunchen.com/algo/array/missing-number.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.