> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/1201-1300/missing-number-in-arithmetic-progression.md).

# 1228. Missing Number In Arithmetic Progression

### Description

In some array `arr`, the values were in arithmetic progression: the values `arr[i + 1] - arr[i]` are all equal for every `0 <= i < arr.length - 1`.

A value from `arr` was removed that **was not the first or last value in the array**.

Given `arr`, return *the removed value*.

### Constraints

* `3 <= arr.length <= 1000`
* `0 <= arr[i] <= 105`
* The given array is **guaranteed** to be a valid array.

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/missing-number-in-arithmetic-progression/)
* ProgramCreek
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** arr = \[5, 7, 11, 13]

**Output:** 9

**Explanation:** The previous array was \[5, 7, 9, 11, 13].
{% endtab %}

{% tab title="Example 2" %}
**Input:** arr = \[15, 13, 12]

**Output:** 14

**Explanation:** The previous array was \[15, 14, 13, 12].
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(n). Where n is the length of array arr since in 
 *    the worst case we iterate over the entire array.
 * Space complexity : O(1). Algorithm requires constant space to execute.
 */

class Solution {
    public int missingNumber(int[] arr) {
        int n = arr.length;

        // Get the difference `difference`.
        int difference = (arr[arr.length - 1] - arr[0]) / n;

        // The expected element equals the starting element.
        int expected = arr[0];

        for (int val : arr) {
            // Return the expected value that doesn't match val.
            if (val != expected) return expected;

            // Next element will be expected element + `difference`.
            expected += difference;
        }
        return expected;
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : O(logn).Where n is the length of array arr since 
 *    we cut the search space in half at every iteration.
 * Space complexity : O(1). Algorithm requires constant space to execute.
 */
 
 class Solution {
    public int missingNumber(int[] arr) {
        int n = arr.length;
        int diff = (arr[n-1]-arr[0]) / n;
        
        if(diff == 0) {
            return arr[0];
        }
        
        int low = 0, high = n-1;
        
        while(low <= high) {
            int mid = low + (high-low)/2;
            if(arr[mid] == arr[0] + mid * diff) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        
        return arr[0] + low * diff;
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*