Last Updated: 15 Jun, 2021

Smallest divisor

Moderate

Asked in companies

Solve now

Problem statement

You are given an array of integers 'arr' and an integer 'limit'.

Your task is to find the smallest positive integer divisor, such that upon dividing all the elements of the given array by it, the sum of the division's result is less than or equal to the given integer's limit.

Note:

Each result of the division is rounded to the nearest integer greater than or equal to that element. For Example, 7/3 = 3.

Input format :

The first line contains an integer ‘n’ denoting the number of elements in the array.

The second line contains ‘n’ Space-separated integers denoting the elements of the array.

The third line contains an integer ‘limit’ denoting the given 'limit'.

Output format :

Print an integer denoting the minimum divisor.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

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.

Solve now