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

  • nn: nums의 길이
  • mm: nums의 최댓값
  • Time: O(nlog(m))O(n \cdot log(m))
  • Space: O(1)O(1)