How to Answer: How can you minimize the maxOperations penalty?
Advice and answer examples written specifically for a Java Intermediate Level Binary Search job interview.
3. How can you minimize the maxOperations penalty?
This interview question concentrates on the developer's skills with Java 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.
class Solution {
public int minimumSize(int[] nums, int maxOperations) {
int left = 1;
int right = Arrays.stream(nums).max().getAsInt();
while(left < right) {
int mid = left + (right -left) / 2;
if (canDo(mid, nums, maxOperations)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
public boolean canDo(int penalty, int[] nums, int maxOperations) {
int operationsCount = 0;
for (int num : nums) {
// Typecasting int to double to get values after decimal
double count = (double)num / (double)penalty;
count = Math.ceil(count) - 1;
operationsCount += (int)count;
}
return operationsCount <= maxOperations;
}
}Time complexity- O(log (max-possible))
Space complexity- O(1)
Written by Jennie Taylor on May 22nd, 2021