Company: Coding Blocks
Difficulty: medium
Minimum Divisor You are given an array of integers. Given an integer x , define array b of size n such that b[i] = a[i] + x and b[i] is an integer and as large as possible. Define f(x) as the sum of all elements of b . Determine the smallest positive x such that f(x) ≤ k . It can be proven that there exists a unique array b given array a and integer x . Input Format The first line contains n and k . The second line contains n elements, the array a . Output Format Print the smallest positive x such that f(x) ≤ k . Constraints 1 ≤ n ≤ 10 5 1 ≤ k ≤ 10 9 1 ≤ a[i] ≤ 10 9 Examples Input: 3 8 1 5 7 Output: 2 Consider x = 2 : Array b = [0, 2, 3] f(x) = 5 It can be shown that selecting x as anything smaller than 2 will result in f(x) > 8 .