Missing Number In Arithmetic Progression

🏠 ⬅️ ➡️

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.

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

Constraints:

  • 3 <= arr.length <= 1000
  • 0 <= arr[i] <= 105
  • The given array is guaranteed to be a valid array.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 5
    integer, dimension(n) :: arr
    integer :: i

    ! Example 1
    arr = [5, 7, 11, 13]
    call solve(arr)
    write (*, '(I0)') arr(3)

    ! Example 2
    arr = [15, 13, 12]
    call solve(arr)
    write (*, '(I0)') arr(2)

contains

    subroutine solve(arr)
        implicit none
        integer, dimension(:), intent(inout) :: arr
        integer :: diff, i

        diff = arr(2) - arr(1)
        do i = 2, size(arr) - 1
            if (arr(i + 1) - arr(i) /= diff) then
                arr(i) = arr(i) + diff
                exit
            end if
        end do
    end subroutine solve
end program main
❌ Compiled
❌ Executed
❌ Correct 
program remove_value
      implicit none

      integer, parameter :: int64 = selected_int_kind(13)

      integer(int64), dimension(:), allocatable :: arr
      integer(int64) :: i, n, removed_value

      read(*,*) n

      allocate(arr(n))

      do i = 1, n
         read(*,*) arr(i)
      end do

      removed_value = solve(arr, n)

      write(*,*) removed_value

      contains

      function solve(arr, n) result(removed_value)
      implicit none

      integer(int64), dimension(n), intent(in) :: arr
      integer(int64), intent(in) :: n
      integer(int64) :: i, diff

      removed_value = 0

      do i = 2, n - 1
         diff = arr(i + 1) - arr(i)
         if (diff /= arr(i - 1) - arr(i)) then
            removed_value = arr(i)
            exit
         end if
      end do

      end function solve

      end program remove_value
🌐 Data from online sources 
def mctFromLeafValues(arr: List[int]) -> int:
    n = len(arr)
    dp = [[0] * n for _ in range(n)]
    maxs = [[0] * n for _ in range(n)]

    for i in range(n):
        for j in range(i, n):
            maxs[i][j] = max(arr[i:j+1])

    for len_ in range(1, n):
        for i in range(n - len_):
            j = i + len_
            dp[i][j] = float('inf')
            for k in range(i, j):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + maxs[i][k] * maxs[k+1][j])

    return dp[0][n - 1]

The algorithm uses dynamic programming to find the smallest possible sum of non-leaf nodes. The 'dp' matrix stores the minimum sum for each sub-array within the input array 'arr'. The 'maxs' matrix stores the maximum values for each sub-array of 'arr'. To fill up the 'dp' matrix, the code iterates through sub-arrays of increasing length and uses previously computed values to find the minimum sum. It tries all possible binary trees using a nested loop and selects the one with the smallest sum. At the end, it returns the minimum sum of non-leaf nodes for the whole array, which is stored in dp[0][n-1].

🌐 Data from online sources 
int mctFromLeafValues(vector<int>& arr) {
    int n = arr.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    vector<vector<int>> maxs(n, vector<int>(n, 0));

    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            maxs[i][j] = *max_element(arr.begin() + i, arr.begin() + j + 1);
        }
    }

    for (int len = 1; len < n; ++len) {
        for (int i = 0; i + len < n; ++i) {
            int j = i + len;
            dp[i][j] = INT_MAX;
            for (int k = i; k < j; ++k) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + maxs[i][k] * maxs[k + 1][j]);
            }
        }
    }
    return dp[0][n - 1];
}

The algorithm uses dynamic programming to find the smallest possible sum of non-leaf nodes. The 'dp' matrix stores the minimum sum for each sub-array within the input array 'arr'. The 'maxs' matrix stores the maximum values for each sub-array of 'arr'. To fill up the 'dp' matrix, the code iterates through sub-arrays of increasing length and uses previously computed values to find the minimum sum. It tries all possible binary trees using a nested loop and selects the one with the smallest sum. At the end, it returns the minimum sum of non-leaf nodes for the whole array, which is stored in dp[0][n-1].