Missing Number In Arithmetic Progression

class Solution {
public:
    int findMissingNumber(vector<int> &nums) {
        int size = nums.size();

        // Calculate common difference
        int step = (nums.back() - nums.front()) / size;
        int low = 0;
        int high = size - 1;

        // Binary search implementation
        while (low < high) {
            int middle = (low + high) / 2;

            // Condition to check continuity in elements using the calculated step
            if (nums[middle] == nums.front() + middle * step) {
                low = middle + 1;
            } else {
                high = middle;
            }
        }

        // The missing number based on its expected position
        return nums.front() + step * low;
    }
};

This solution tackles the problem of finding a missing number in an arithmetic sequence using a C++ implementation that leverages binary search for efficiency. The sequence is passed as a vector of integers.

1. Start by determining the size of the vector called nums.
2. Compute the common difference of the sequence, which is (nums.back() - nums.front()) / size. This calculation uses the first and the last elements of the sequence.
3. Initialize two pointers, low and high, which help in navigating the binary search. Initially, low is set to 0 and high to size - 1.
4. Implement a binary search loop that continues until low is less than high. Inside the loop:
   • Calculate the midpoint (middle) as (low + high) / 2.
   • Following the arithmetic sequence formula, check if nums[middle] is precisely what it should be if there were no number missing (nums.front() + middle * step). If this condition is true, adjust the low pointer to middle + 1, else adjust the high pointer to middle.
5. Calculate and return the missing number using nums.front() + step * low after the loop completes. This formula estimates the missing number based on its expected position in the sequence.

This approach efficiently pinpoints the location of the missing number in log(n) time complexity due to the binary search mechanism, making it highly suitable for large sequences.

class Solution {
    public int findMissing(int sequence[]) {
        int size = sequence.length;
        int step = (sequence[size - 1] - sequence[0]) / size;
        int start = 0;
        int end = size - 1;

        while (start < end) {
            int middle = (start + end) / 2;

            if (sequence[middle] == sequence[0] + middle * step) {
                start = middle + 1;
            } else {
                end = middle;
            }
        }

        return sequence[0] + step * start;
    }
}

In this Java solution, the task is to find the missing number in an arithmetic progression. The code defines a class Solution with the method findMissing which accepts an integer array sequence. Here's how the solution works step-by-step:

1. Calculate the length of the sequence array and store it in size.
2. Compute the common difference step of the progression using the formula (sequence[size - 1] - sequence[0]) / size.
3. Initialize two pointers: start at the beginning of the sequence and end at the end of the sequence.
4. Use a binary search approach to determine the missing element. The search is conducted within the boundaries set by start and end:
   • Calculate the middle index middle using the average of start and end.
   • If the value at the middle index matches the expected value of an arithmetic sequence (sequence[0] + middle * step):
     • Move the start index to middle + 1.
   • Otherwise:
     • Adjust the end to middle.
5. Exit the while loop once start is not less than end.
6. The missing number is found by plugging start into the formula for the terms of the arithmetic sequence sequence[0] + step * start.

The algorithm efficiently locates the missing number by narrowing down the search range using the arithmetic properties of the sequence. The use of binary search ensures that the time complexity is logarithmic, making it suitable for large sequences.