Problem

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.

Examples

Example 1:

1
2
3

Input: arr = [5,7,11,13]
Output: 9
Explanation: The previous array was [5,7,**9** ,11,13].

Example 2:

1
2
3

Input: arr = [15,13,12]
Output: 14
Explanation: The previous array was [15,**14** ,13,12].

Constraints:

  • 3 <= arr.length <= 1000
  • 0 <= arr[i] <= 10^5
  • The given array is guaranteed to be a valid array.

Solution

Method 1 – Find the Missing Value by Common Difference

Intuition

In an arithmetic progression, the difference between consecutive elements is constant. Since one value (not first or last) is missing, most consecutive differences will be equal except for one place where the gap is twice the common difference. By finding the smallest difference and locating the anomaly, we can recover the missing value.

Approach

  1. Compute the common difference by taking the minimum of all consecutive differences.
  2. Iterate through the array and find where the difference between arr[i+1] and arr[i] is not equal to the common difference.
  3. The missing value is arr[i] + common difference at that position.
  4. Return the missing value.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int missingNumber(vector<int>& arr) {
        int n = arr.size();
        int d = min(arr[1] - arr[0], arr[2] - arr[1]);
        for (int i = 0; i < n - 1; ++i) {
            if (arr[i+1] - arr[i] != d) return arr[i] + d;
        }
        return -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func MissingNumber(arr []int) int {
    n := len(arr)
    d := arr[1] - arr[0]
    if arr[2]-arr[1] < d {
        d = arr[2] - arr[1]
    }
    for i := 0; i < n-1; i++ {
        if arr[i+1]-arr[i] != d {
            return arr[i] + d
        }
    }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int missingNumber(int[] arr) {
        int n = arr.length;
        int d = Math.min(arr[1] - arr[0], arr[2] - arr[1]);
        for (int i = 0; i < n - 1; i++) {
            if (arr[i+1] - arr[i] != d) return arr[i] + d;
        }
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    fun missingNumber(arr: IntArray): Int {
        val n = arr.size
        val d = minOf(arr[1] - arr[0], arr[2] - arr[1])
        for (i in 0 until n - 1) {
            if (arr[i+1] - arr[i] != d) return arr[i] + d
        }
        return -1
    }
}
1
2
3
4
5
6
7
8
9

from typing import List
class Solution:
    def missingNumber(self, arr: List[int]) -> int:
        n = len(arr)
        d = min(arr[1] - arr[0], arr[2] - arr[1])
        for i in range(n - 1):
            if arr[i+1] - arr[i] != d:
                return arr[i] + d
        return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn missing_number(arr: Vec<i32>) -> i32 {
        let n = arr.len();
        let d = (arr[1] - arr[0]).min(arr[2] - arr[1]);
        for i in 0..n-1 {
            if arr[i+1] - arr[i] != d {
                return arr[i] + d;
            }
        }
        -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    missingNumber(arr: number[]): number {
        const n = arr.length;
        const d = Math.min(arr[1] - arr[0], arr[2] - arr[1]);
        for (let i = 0; i < n - 1; i++) {
            if (arr[i+1] - arr[i] !== d) return arr[i] + d;
        }
        return -1;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — We scan the array once to find the anomaly.
  • 🧺 Space complexity: O(1) — Only a few variables are used for computation.