#include <stdio.h>
 
// Function to find missing term in a sequence
int missingTerm(int A[], int n)
{
    // search space is A[low..high]
    int low = 0, high = n - 1;
 
    // calculate common difference between successive elements
    int d = (A[n - 1] - A[0]) / n;
 
    // run till search space is exhausted
    while (low <= high)
    {
        // find middle index
        int mid = high - (high - low) / 2;
 
        // check difference of mid element with its right neighbor
        if (mid + 1 < n && A[mid + 1] - A[mid] != d)
            return A[mid + 1] - d;
 
        // check difference of mid element with its left neighbor
        if (mid - 1 >= 0 && A[mid] - A[mid - 1] != d)
            return A[mid - 1] + d;
 
        // if missing element lies on left sub-array, then we reduce
        // our search space to left sub-array A[low..mid-1]
        if (A[mid] - A[0] != (mid - 0) * d)
            high = mid - 1;
 
        // if missing element lies on right sub-array, then reduce
        // our search space to right sub-array A[mid+1..high]
        else
            low = mid + 1;
    }
}
 
// Find missing term in a sequence
int main(void)
{
    int A[] = { 5, 7, 9, 11, 15 };
    int n = sizeof(A) / sizeof(A[0]);
 
    printf("Missing element is %d", missingTerm(A, n));
 
    return 0;
}

I2luY2x1ZGUgPHN0ZGlvLmg+CgovLyBGdW5jdGlvbiB0byBmaW5kIG1pc3NpbmcgdGVybSBpbiBhIHNlcXVlbmNlCmludCBtaXNzaW5nVGVybShpbnQgQVtdLCBpbnQgbikKewogICAgLy8gc2VhcmNoIHNwYWNlIGlzIEFbbG93Li5oaWdoXQogICAgaW50IGxvdyA9IDAsIGhpZ2ggPSBuIC0gMTsKCiAgICAvLyBjYWxjdWxhdGUgY29tbW9uIGRpZmZlcmVuY2UgYmV0d2VlbiBzdWNjZXNzaXZlIGVsZW1lbnRzCiAgICBpbnQgZCA9IChBW24gLSAxXSAtIEFbMF0pIC8gbjsKCiAgICAvLyBydW4gdGlsbCBzZWFyY2ggc3BhY2UgaXMgZXhoYXVzdGVkCiAgICB3aGlsZSAobG93IDw9IGhpZ2gpCiAgICB7CiAgICAgICAgLy8gZmluZCBtaWRkbGUgaW5kZXgKICAgICAgICBpbnQgbWlkID0gaGlnaCAtIChoaWdoIC0gbG93KSAvIDI7CgogICAgICAgIC8vIGNoZWNrIGRpZmZlcmVuY2Ugb2YgbWlkIGVsZW1lbnQgd2l0aCBpdHMgcmlnaHQgbmVpZ2hib3IKICAgICAgICBpZiAobWlkICsgMSA8IG4gJiYgQVttaWQgKyAxXSAtIEFbbWlkXSAhPSBkKQogICAgICAgICAgICByZXR1cm4gQVttaWQgKyAxXSAtIGQ7CgogICAgICAgIC8vIGNoZWNrIGRpZmZlcmVuY2Ugb2YgbWlkIGVsZW1lbnQgd2l0aCBpdHMgbGVmdCBuZWlnaGJvcgogICAgICAgIGlmIChtaWQgLSAxID49IDAgJiYgQVttaWRdIC0gQVttaWQgLSAxXSAhPSBkKQogICAgICAgICAgICByZXR1cm4gQVttaWQgLSAxXSArIGQ7CgogICAgICAgIC8vIGlmIG1pc3NpbmcgZWxlbWVudCBsaWVzIG9uIGxlZnQgc3ViLWFycmF5LCB0aGVuIHdlIHJlZHVjZQogICAgICAgIC8vIG91ciBzZWFyY2ggc3BhY2UgdG8gbGVmdCBzdWItYXJyYXkgQVtsb3cuLm1pZC0xXQogICAgICAgIGlmIChBW21pZF0gLSBBWzBdICE9IChtaWQgLSAwKSAqIGQpCiAgICAgICAgICAgIGhpZ2ggPSBtaWQgLSAxOwoKICAgICAgICAvLyBpZiBtaXNzaW5nIGVsZW1lbnQgbGllcyBvbiByaWdodCBzdWItYXJyYXksIHRoZW4gcmVkdWNlCiAgICAgICAgLy8gb3VyIHNlYXJjaCBzcGFjZSB0byByaWdodCBzdWItYXJyYXkgQVttaWQrMS4uaGlnaF0KICAgICAgICBlbHNlCiAgICAgICAgICAgIGxvdyA9IG1pZCArIDE7CiAgICB9Cn0KCi8vIEZpbmQgbWlzc2luZyB0ZXJtIGluIGEgc2VxdWVuY2UKaW50IG1haW4odm9pZCkKewogICAgaW50IEFbXSA9IHsgNSwgNywgOSwgMTEsIDE1IH07CiAgICBpbnQgbiA9IHNpemVvZihBKSAvIHNpemVvZihBWzBdKTsKCiAgICBwcmludGYoIk1pc3NpbmcgZWxlbWVudCBpcyAlZCIsIG1pc3NpbmdUZXJtKEEsIG4pKTsKCiAgICByZXR1cm4gMDsKfQ==