Minimum Limit of Balls in a Bag
MediumArrayBinary Search
Solution
export function minimumSize(nums: number[], maxOperations: number): number {
const maxNum = nums.reduce((prev, num) => Math.max(prev, num), 0);
let [left, right] = [1, maxNum];
while (left < right) {
const mid = Math.floor((left + right) / 2);
const operations = nums.reduce((acc, num) => acc + getOperation(num, mid), 0);
if (maxOperations < operations) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
function getOperation(num: number, maxPenalty: number) {
return Math.floor((num - 1) / maxPenalty);
}
Complexity
- :
nums
의 길이 - :
nums
의 최댓값 - Time:
- Space: