Задача: 1283. Find the Smallest Divisor Given a Threshold
Сложность: 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.

😎 Решение:
public class Solution {
public int SmallestDivisor(int[] nums, int threshold) {
int maxElement = nums.Max();

for (int divisor = 1; divisor threshold) {
thresholdExceeded = false;
break;
}
}

if (thresholdExceeded) {
return divisor;
}
}

return -1;
}
}

Ставь 👍 и забирай 📚 Базу знаний