PROBLEM LINK:
Author: Mahmoud Badawy
Tester: Mohammed Ehab
DIFFICULTY:
MEDIUM
PREREQUISITES:
Binary Search, Greedy
PROBLEM:
given an array of integers find an order such that the maximum value x that for every element (i+1)*x<=arr[i]
QUICK EXPLANATION:
sort the array then use binary search to find the value
EXPLANATION:
Sort the array because it’s better to assign the smallest value to the smallest i to make (i+1)*x smaller for this value then use binary search to find the maximum value
Complexity: O(n*log(n))
ALTERNATIVE SOLUTION:
Sort the array and for each one find the maximum x he can use as it’s arr[i]/(i+1) then take the minimum between them
Complexity: O(n)
SOLUTIONS:
Binary Search solution can be found here.
Greedy can be found here.