Posts Missing Number In Arithmetic Progression
Post
Cancel

Missing Number In Arithmetic Progression

PROBLEM 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.

leetcode

SOLUTION

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {

    public int missingNumber(int[] arr) {

        int n = arr.length;

        // Calculate the common difference (r) of the arithmetic progression.
        // As per the problem, the first and last numbers cannot be incorrect, so we can use that to find r
        int r = (arr[n-1] - arr[0]) / n;

        // Iterate through the array to find the missing value
        for (int i = 1; i < n; i++) {
            // the next element in the AP should be: previous element + common difference
            if (arr[i-1] + r != arr[i]) {
                // If it's not, return the expected value in the progression
                return arr[i-1] + r;
            }
        }

        return arr[0]; // r=0, case: [x, x, x, x] -> all same elements

    }

}
This post is licensed under CC BY 4.0 by the author.