MAXTIME - editorial

PROBLEM LINK:

Practice
Contest

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.