Smallest divisor

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
115 upvotes
Asked in companies
SalesforceVymo

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
5
1 2 3 4 5
8
Sample Output 1 :
3
Explanation for Sample Input 1 :
We can get a sum of 15(1 + 2 + 3 + 4 + 5) if we choose 1 as a divisor. 
The sum is 9(1 + 1 + 2 + 2 + 3)  if we choose 2 as a divisor, and the sum is 7(1 + 1 + 1 + 2 + 2) if we choose 3 as a divisor, which is less than the 'limit'.
Hence we return 3.
Sample Input 2 :
4
8 4 2 3 
10
Sample Output 2 :
2
Explanation for Sample Input 2:
We can get a sum of 17(8 + 4 + 2 + 3) if we choose 1 as a divisor. 
The sum is 9(4 + 2 + 1 + 2) if we choose 2 as a divisor, which is less than the 'limit'.
Hence, we return 2.
Sample Input 3:
5
2 3 5 7 11
11
Sample Output 3 :
3
Constraints :
1 <= n <= 10 ^ 5
1 <= arr[i] <= 10 ^ 6
N <= limit <= 10 ^ 4

Time Limit: 1 sec.
Hint

Try to find every possible solution and choose the largest of them.

Approaches (2)
Brute Force

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.
Time Complexity

O(N * M), where ‘N’ is the length of the given array, and ‘M’ is the value of the maximum element from the given array.

 

As we are making nested iterations for each element of the array by dividing every element of the array with the integers from 1 to the maximum element of the array. Therefore, the overall time complexity will be O(N * M).

Space Complexity

O(1)

As we are using constant space for the approach. Therefore, the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Smallest divisor
Full screen
Console