# Smallest divisor

Posted: 15 Jun, 2021

Difficulty: Moderate

#### 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.
```

Approach 1

The approach is to find the minimum divisor from 1 to the maximum element of the input array. We keep on selecting the divisor until we get the result.

**Approach :**

- First, find the maximum element from the given array, say ‘mx’.
- Declare a variable ‘sum’ which will store the sum of the modified array.
- Now iterate from 1 to ‘mx’ with the help of the iterator pointer ‘i’.
- Make ‘sum’ = 0 in every iteration of ‘i’.
- Make an iteration to iterate through the array ‘arr’ with an iterator pointer ‘j’ from 0 to the size of the 'N’.
- Modify every element of ‘arr’ by dividing element by ‘i’ and taking the ceil value from it and storing the values in 'modifiedValue'.
- Store the sum of the modified elements.

- If the ‘sum’ is smaller than or equal to the given integer ‘limit’ then break the iteration.

- Return ‘i’ to the function.

Approach 2

The idea is to optimize the search space which is from 1 to 10 ^ 6 by using the binary search technique. Calculate the mid for every search space and accordingly adjust the high and low values.

**Approach :**

- First, calculate the maximum element from the array and store it in a variable, say ‘maxDiv’.
- Initialize the variable ‘minDiv’ to 1, ‘sum’ to 0, and ‘divisor’ to -1.
- Iterate while ‘minDiv’ < ‘maxDiv’.
- Calculate the middle value of ‘minDiv’ and ‘maxDiv’ and store it in a variable, say ‘mid’.
- Make ‘sum’ to 0 for every iteration.
- Make an iteration to iterate over the given array.
- Store the sum of the values of the given array modified as ceil of (arr[i] / mid).

- If the ‘sum’ is found to be greater than the ‘limit’, then make ‘minDiv’ to ‘mid’ + 1.
- Else make ‘maxDiv’ to ‘mid’ - 1 and store the value of ‘mid’ in ‘divisor’.

- Return ‘divisor’ to the given function.