> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/sorting-and-searching/single-missing-number.md).

# Single Missing Number

Given a contiguous sequence of numbers in which each number repeats thrice, there is exactly one missing number. Find the missing number.

```
input: 11122333
output: 2

input: 11122233344455666
output: 5
```

**The Idea:** Because we know that the sequence of numbers are integer continuous, we can model what we expect for the output with the function $$f(x) = int(x/3 + 1)$$, shown below in blue. Then we can perform a binary search to find the missing number. If the middle element is what we expect, then either the missing number exists to the right of it, or the middle element is the missing number. In the case that it is the missing number, the next iteration of binary search will search left to find it.

![](/files/-LoJIgGlAyamIxQnHiz7)

**Complexity:** O(logn) time and space

```cpp
int __bs_findMissingNumber(int left, int right, const vector<int> &nums) {

    if (left < right) {
        int middle = left + (right - left) / 2;
        float expect = (float(middle/3)) + 1;

        if (nums[middle] == floor(expect))
            return __bs_findMissingNumber(middle + 1, right, nums);
        else
            return __bs_findMissingNumber(left, middle - 1, nums);
    }
    else {
        return nums[left]; // left == right
    }
}


int findMissingNumber(const vector<int> &nums) {
    if (nums.size() < 3)
        return 1;
    return __bs_findMissingNumber(0, nums.size() - 1, nums);
}


int main()
{
    vector<int> nums1 = { 1,1,1,2,2,2,3,3,3,4,4,4,5,5,6,6,6 };
    vector<int> nums2 = { 1,1,1,2,2,3,3,3 };
    vector<int> nums3 = {};
    vector<int> nums4 = { 1,1 };
    vector<int> nums6 = { 1,1,1,2 };
    vector<int> nums7 = { 1,1,1,2,2, };
    vector<int> nums9 = { 1,1,1,2,2,2,3,3,3,4 };

    cout << 1 << ' ' << findMissingNumber(nums1) << endl;
    cout << 2 << ' ' << findMissingNumber(nums2) << endl;
    cout << 3 << ' ' << findMissingNumber(nums3) << endl;
    cout << 4 << ' ' << findMissingNumber(nums4) << endl;
    cout << 6 << ' ' << findMissingNumber(nums6) << endl;
    cout << 7 << ' ' << findMissingNumber(nums7) << endl;
    cout << 9 << ' ' << findMissingNumber(nums9) << endl;
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/sorting-and-searching/single-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.