How to Answer: How can you minimize the maxOperations penalty?
Advice and answer examples written specifically for a JavaScript Intermediate Level Binary Search job interview.
3. How can you minimize the maxOperations penalty?
This question focuses on the developer's knowledge of JavaScript functions and binary search.
There are n bags. Each bag contains some number of balls given by array nums. The ith bag contains nums[i] number of balls. You need to do some operations on the array. In one operation, you take a bag and divide it into two bags containing a positive number of balls. For example, if you had a bag with 6 balls, you can do one operation and divide it into two bags containing 2 and 4 balls. You are also given an input parameter maxOperations which is the maximum number of operations that you can perform.
The penalty on all the bags is the maximum number of balls in a bag. Your task is to minimize the penalty in maxOperations number of operations.
/*Example*/
nums = [7, 6, 17] maxOperations = 2
expected output = 7
explanation:-
after first operation:- [7, 6, 7, 10]
after second operation:- [7, 6, 7, 7, 3]
the maximum number of balls is 7. So the penalty is 7.Solution:
We can use binary search for it. Let’s say min is the minimum penalty that is possible using maxOperations. If we are asked:
â— Can we have a penalty of less than min? The answer is no.
â— Can we have a penalty greater than or equal to min? The answer is definitely yes.
1 2 … min - 1 min min + 1 … max-possible
F F F F T T T T
We will do the binary search from 1 to max-possible. The value of max-possible is the maximum penalty that we can have which is the penalty before any operation. The function canDo returns if we can have a penalty using maxOperations.
/**
* @param {number[]} nums
* @param {number} maxOperations
* @return {number}
*/
function minimumPenalty(nums, maxOperations) {
let left = 1
let right = Math.max(...nums)
while(left < right) {
let mid = (left + right) / 2
mid = Math.floor(mid)
if (canDo(mid, nums, maxOperations)) {
right = mid
} else {
left = mid + 1
}
}
return left
}
function canDo(penalty, nums, maxOperations) {
let operationsCount = 0
for (const num of nums) {
let count = num / penalty
count = Math.ceil(count) - 1
operationsCount += count
}
return operationsCount <= maxOperations
}Time complexity- O(n log (max-possible))
Space complexity- O(1)
Written by S. Kumar on May 22nd, 2021