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

• ProgramCreek

• YouTube

Examples

Example 1

Input: arr = [5, 7, 11, 13]

Output: 9

Explanation: The previous array was [5, 7, 9, 11, 13].

Example 2

Solutions

Solution 1

/**
 * 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;
    }
}

Solution 2

Follow up