0

Smallest divisor

Difficulty: MEDIUM
Avg. time to solve
20 min
Success Rate
70%

Problem Statement

Ninja is on his way to learn about Divisors in mathematics So he encountered a problem in which the statement is “You are given an array 'arr 'of integers and an integer 'limit'. Your task is to find the minimum integer such that if you divide the whole array with that integer then the sum of the array should be less than or equal to the given integer 'limit'.

Ninja is very new to such kinds of problems so he wants your help. Help Ninja!

Note:

Each result of the division should be rounded off to the nearest integer greater than or equal to that element. (eg : 5 / 2 = 2.5 rounded off to 3 and 10 / 3 = 3.33 rounded off to 4).

Input format :

The first line of input contains an integer ‘T’, which denotes the number of test cases. Then each test case follows. 

The first line of each test case contains an integer ‘N’ denoting the number of elements in the array .

The second line of each test case contains ‘N’ Space-separated integers denoting the elements of array.

The third Line of each test contains an integer ‘limit’ denoting the given 'limit'.

Output format :

For each test case print an integer denoting the minimum divisor.

The output of each test case will be printed on a separate line.

Constraints :

1 <= T <= 5
1 <= N <= 2 * (10 ^ 3)
1 <= arr[i] <= 10 ^ 3
N <= limit <= 10 ^ 4

Time Limit: 1 sec.

Note :

You don’t need to print anything, it has already been taken care of. Just implement the given function.
Sample Input 1 :
2
5
1 2 3 4 5
8  
4
8 4 2 3 
10
Sample Output 1 :
3
2
Explanation for Sample Input 1 :
Test Case 1: 
We can get a sum 15(1 + 2 + 3 + 4 + 5) if we choose 1 as a divisor,
9(1 + 1 + 2 + 2 + 3)  if we choose 2 as a divisor,
5(0 + 1 + 1 + 1 + 2) if we choose 3 as a divisor,

Test Case 2:
We can get a sum 17(8 + 4 + 2 + 3) if we choose 1 as a divisor,
9(4 + 2 + 1 + 2) if we choose 2 as a divisor,
Sample Input 2 :
2
4
1 2 5 9
6  
5
2 3 5 7 11
11
Sample Output 2 :
5
3
Reset Code
Full screen
copy-code
Console