Missing Number In Arithmetic Progression Solutions in C++

/// Source : https://leetcode.com/problems/missing-number-in-arithmetic-progression/
/// Author : liuyubobobo
/// Time   : 2019-10-19

#include <iostream>
#include <vector>

using namespace std;


/// Linear Scan and find the max gap between numbers
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    int missingNumber(vector<int>& arr) {

        int maxGap = arr[1] - arr[0], start = 0;
        for(int i = 2; i < arr.size(); i ++)
            if(abs(arr[i] - arr[i - 1]) > abs(maxGap)){
                maxGap = arr[i] - arr[i - 1];
                start = i -1;
            }
        return arr[start] + maxGap / 2;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/missing-number-in-arithmetic-progression/
/// Author : liuyubobobo
/// Time   : 2019-10-19

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;


/// Using mathematics to calculate difference first
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    int missingNumber(vector<int>& arr) {

        int d = (arr.back() - arr[0]) / (int)arr.size();
        for(int i = 1; i < arr.size(); i ++)
            if(arr[i] != arr[i - 1] + d) return arr[i - 1] + d;

        // a tricky case is d == 0
        assert(d == 0);
        return arr[0];
    }
};


int main() {

    vector<int> arr1 = {15, 13, 12};
    cout << Solution().missingNumber(arr1) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/missing-number-in-arithmetic-progression/
/// Author : liuyubobobo
/// Time   : 2019-10-19

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;


/// Binary Search
/// Time Complexity: O(logn)
/// Space Complexity: O(1)
class Solution {
public:
    int missingNumber(vector<int>& arr) {

        int d = (arr.back() - arr[0]) / (int)arr.size();
        int l = 0, r = arr.size() - 1;
        while(l < r){
            int mid = (l + r) / 2;
            int num = arr[0] + mid * d;
            if(num != arr[mid])
                r = mid;
            else
                l = mid + 1;
        }
        return arr[l] - d;
    }
};


int main() {

    vector<int> arr1 = {15, 13, 12};
    cout << Solution().missingNumber(arr1) << endl;
    // 14

    return 0;
}