Problem Brief

Get Minimum Increment

See IBM online assessment and hiring insights

Given an integer array arr of length n, you can perform the following operation on the array at most once:

Choose a subset of elements from the array such that no two selected elements are adjacent (i.e., no two selected elements are next to each other in the array).

Choose a non-negative integer x, and increase all the selected elements by x.

Determine the minimum non-negative integer x, required to make the array arr non-decreasing using at most one operation. If it is impossible, return -1.

Function Description

Complete the function getMinimumIncrement in the editor with the following parameter(s):

int arr[n]: the array

Returns

int: the minimum value of increment so that the array becomes non-decreasing

1Example 1

Input

arr = [1, 1, 3, 2]

Output

Explanation

Some of the possible ways are:

Select the element with index 3 (0-based indexing) and increment = 1 to get the array arr = [1, 1, 3, 3].
Select the elements with indices [1, 3] (0-based indexing) and increment = 2 to get the array arr = [1, 3, 3, 4].

Hence, the minimum value of increment is 1.