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.

Complexity: O(logn) time and space

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;
}