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

Input: arr = [15, 13, 12]

Output: 14

Explanation: The previous array was [15, 14, 13, 12].

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

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

Follow up