Сложность: medium
Дан массив целых чисел nums и целое число threshold. Мы выберем положительный целый делитель, разделим все элементы массива на него и суммируем результат деления. Найдите наименьший делитель, такой что результат, упомянутый выше, меньше или равен threshold.
Каждый результат деления округляется до ближайшего большего целого числа. (Например: 7/3 = 3 и 10/2 = 5).
Гарантируется, что решение существует.
Пример:
Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1.
If the divisor is 4 we can get a sum of 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2).
👨💻 Алгоритм:
1⃣Найдите максимальный элемент массива nums и сохраните его в переменной maxElement.
2⃣Итерация по всем делителям от 1 до maxElement:
Инициализируйте две переменные: sumOfDivisionResults для хранения суммы результатов деления и thresholdExceeded для указания, превышен ли порог.
Итерация по всем элементам массива nums: добавьте результат деления, округленного до ближайшего большего целого числа, в переменную sumOfDivisionResults. Если сумма превышает threshold, установите thresholdExceeded в true и прекратите итерацию по массиву nums.
3⃣Проверьте, был ли превышен порог:
Если порог не был превышен, текущий делитель является наименьшим делителем, поэтому верните его.
Если не найдено возможного делителя, верните -1.
😎 Решение:
class Solution {
function smallestDivisor($nums, $threshold) {
$maxElement = max($nums);
for ($divisor = 1; $divisor <= $maxElement; $divisor++) {
$sumOfDivisionResults = 0;
$thresholdExceeded = true;
foreach ($nums as $num) {
$sumOfDivisionResults += ceil($num / $divisor);
if ($sumOfDivisionResults > $threshold) {
$thresholdExceeded = false;
break;
}
}
if ($thresholdExceeded) {
return $divisor;
}
}
return -1;
}
}Ставь 👍 и забирай 📚 Базу знаний