How should I practice Ice Cream Sticks?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Intuit online assessment problems in FastPrep.

Is Ice Cream Sticks associated with Intuit?

FastPrep tags this as a Intuit coding interview or online assessment practice problem when the problem catalog has that company context.

FastPrep

Problem · Array

Ice Cream Sticks

● MediumIntuitINTERNOA

Given an array A[] denoting heights of N ice cream sticks and a positive integer K, modify the height of each stick either by increasing or decreasing them by K only once and then find out the least difference in the heights between the shortest and longest sticks.

For example, consider that the heights are 0, 6, 11 and K=7. We can change 0 to 7, 6 to 9, and 11 to 4. The maximum difference is between 4 and 9, which is 5. We cannot minimise this difference.

Input

The first line of input contains a positive integer K. The second line of input contains a positive integer N, representing the number of sticks. The third line of the input contains N integers, representing the heights of N sticks.

Output

The minimum of the maximum difference of heights possible.

Examples

01 · Example 1

K = 2
A = [2, 6, 9, 11]
return = 5

Explanation: 2->4, 6->8, 9->7, 11->9. So, the maximum difference is 5 (9-4).

02 · Example 2

K = 20
A = [3, 4, 5]
return = 2

3->23, 4->24, 5->25. So, the max different is 2(25-23).

Constraints

0 < K <= 30
0 < N <= 30
0 <= A[i] <= 500