Problem overview
The method minTime receives an Array[Int] named times, where each element is how many time units one worker needs to pack a single product, and an Int named K. All workers pack at once. The method returns the smallest time in which they pack at least K products in total.
For times = [4, 7, 3, 6, 7, 1] and K = 60, the answer is 30. In 30 units the workers pack 7 + 4 + 10 + 5 + 4 + 30 = 60 products. In 29 units they pack 57, which isn't enough.
The statement asks for O(n * log(k * T)) time and O(1) extra space. Counting up one time unit at a time, as the first version of this problem does, takes time proportional to the answer, which is too slow when the answer is large.
Approach: binary search on the answer
The number of products packed in time units is the sum of time / t over all workers, with integer division. This total never decreases as time grows. So every time is either "too short" (fewer than K products) or "enough" (at least K), and all the too-short times come before all the enough times. The answer is the first enough time, the boundary between the two groups.
That is the same structure binary search handles in a sorted array. The "array" here is the range of possible times, and the "element" at a time is whether the workers pack enough in it. You test the middle time, then discard the half that can't hold the boundary.
The search range needs two ends:
- The lower end is 1. (A time of 0 packs nothing, so it only helps when
Kis 0.) - The upper end is
minValue * K, whereminValueis the smallest element oftimes. The fastest worker alone packsKproducts in exactly that time, so the group is certainly done by then.
Step by step
- Find
minValue, the smallest element oftimes, by starting attimes(0)and lowering it withmath.minin a loop. - Set
left = 1andright = minValue * K. Create avar time = 0that will hold the best (smallest) enough time found so far. - Loop while
left <= right. - Take
mid = (left + right) / 2. - If
countProducts(times, mid) < K, thenmidis too short, and so is every smaller time. Setleft = mid + 1. - Otherwise
midis enough. Record it withtime = mid, then look for something shorter withright = mid - 1. - When the loop ends,
timeholds the smallest enough time.
Recording mid before shrinking the range is important. The loop may end on a middle value that was too short, so the last good value has to be remembered. The helper countProducts loops over times and adds time / t for each worker t.
The solution in Scala
class Solution {
def countProducts(times: Array[Int], time: Int): Int = {
var products = 0
for (t <- times) {
products += time / t
}
products
}
def minTime(times: Array[Int], K: Int): Int = {
var minValue = times(0)
for (t <- times) {
minValue = math.min(minValue, t)
}
var left = 1
var right = minValue * K
var time = 0
while (left <= right) {
val mid = (left + right) / 2
if (countProducts(times, mid) < K) {
left = mid + 1
} else {
time = mid
right = mid - 1
}
}
time
}
}
Scala details
Arrays are indexed with parentheses, so the first element is times(0). for (t <- times) visits each value, and math.min comes from the scala.math package, which is available without an import.
Variables that change, minValue, left, right, time and products, are vars. mid is a val because every iteration creates a new one.
The methods end with a bare variable name, products or time. In Scala the last expression of a block is its value, so no return is written.
Integer division in time / t truncates, so a worker who needs 7 units per product has packed 4 products after 29 units, since 29 / 7 is 4.
An Int is 32 bits and overflow wraps silently, with no error. Two spots can be affected: minValue * K and the total from countProducts. The edge cases below show an input where the upper end overflows.
Complexity
Time: finding the minimum takes O(n). The binary search halves a range of size minValue * K, so it makes about log(minValue * K) iterations, and each calls countProducts for O(n) work. The total is O(n * log(K * T)), where T stands for the fastest worker's time, in line with the bound in the statement.
Space: a few integer variables, so O(1).
Edge cases and common mistakes
- Not recording the answer. Returning
leftorrightwithout a savedtimeis error-prone. The code above keeps the last "enough" middle value intime, and that is the result. - Wrong direction. If
midpacks fewer thanKproducts, the answer is larger, so moveleftup. If it packs enough, the answer ismidor smaller, so moverightdown. Swapping them sends the search the wrong way. - One worker. With
times = [5]andK = 1, the range is[1, 5], and the answer is 5. - K is zero. The upper end is 0, so the loop never runs and the method returns 0.
- Several workers. For
[2, 5]andK = 7the answer is 10, found by searching[1, 14]. - Overflow of the upper end. If the answer doesn't fit in an
Int, the bound is wrong. For example,60000 * 50000evaluates to-1294967296, so a single worker withtimes = [60000]andK = 50000gets a negativeright, the loop never runs, and the method returns 0 instead of 3,000,000,000. UsingLongfor the time values fixes this when the inputs can be that large. - Empty array.
times(0)throws anArrayIndexOutOfBoundsException. The problem assumes at least one worker.
Testing
[4, 7, 3, 6, 7, 1]withK = 60gives 30.[5]withK = 1gives 5.[2, 5]withK = 7gives 10.[3, 3]withK = 0gives 0.
