Problem overview
The function minTime receives an IntArray called times and an Int called K. Worker i needs times[i] units of time to pack one product. All workers pack at once, each at their own pace. The function returns the smallest amount of time after which the workers have packed 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 and 30 products, which is exactly 60. In 29 units they pack 7 + 4 + 9 + 4 + 4 + 29 = 57, which is not enough.
A worker who needs t units per product packs time / t products in time units, rounded down, because an unfinished product doesn't count.
Approach: try each time in turn
This lesson is the plain version. Start at time 0 and ask "how many products can the workers pack in this much time?". If the answer is still below K, add one unit and ask again. The first time that reaches K is the minimum.
This works because the total can never shrink as time grows: every worker's count either stays the same or goes up. The first time at which the total reaches K is therefore the smallest time at which it is at least K, and all later times also qualify.
The cost is high. Every candidate time costs a pass over all n workers, and the number of candidates can be as large as the answer itself. With one worker who needs 1000 units per product and K = 1000000, the loop tests a billion different times. The statement writes the budget as O(n * k * T), which signals that this is the slow, brute-force baseline. A later lesson on the same problem replaces the one-unit steps with a binary search on the answer.
Step by step
- Declare
timewithvarand start it at 0. It changes every iteration, sovalwould not compile. - Loop while the workers are short. The helper
countProducts(times, time)returns how many products everyone packs intimeunits. The loop runs while that count is less thanK. - Add one unit of time with
time++in the loop body. - Return
timewhen the loop stops. It is the first time at which the count reachedK. - Write the helper above
minTimeasfun countProducts(times: IntArray, time: Int): Int. - Start a
var productsat 0 to hold the running total. - Loop over the workers with
for (t in times), wheretis one worker's time per product. - Add
time / ttoproducts. Dividing twoInts already drops the fraction, which is the rounding down the problem needs. - Return
productsafter the loop.
The solution in Kotlin
class Solution {
fun countProducts(times: IntArray, time: Int): Int {
var products = 0
for (t in times) {
products += time / t
}
return products
}
fun minTime(times: IntArray, K: Int): Int {
var time = 0
while (countProducts(times, time) < K) {
time++
}
return time
}
}
The Kotlin details worth a closer look:
for (t in times). This loops over the values of the array directly, with no index. Usetimes.indicesonly when the position matters.- Integer division. For two
Ints,/truncates, so29 / 4is 7 and29 / 7is 4. If you want a fractional result you have to convert one side toDouble. products += .... Compound assignment is allowed on avar. Writing it on avalis a compile error.time++as a statement. Kotlin has the increment operator for variables. It is a statement here, not a value you need to use.- A capital parameter name.
Kis a legal parameter name; Kotlin style prefers lowercase, but the lesson keeps the name from the statement.
Complexity
Time: proportional to the answer times n. Each call to countProducts is O(n), and the loop makes one call per candidate time from 0 up to the answer, which is at most min(times) * K. In the worst case that is O(n * K * T) with T the smallest time, matching the statement's budget. It is fine for small inputs and far too slow when K or the times are large.
Space: O(1). The code keeps a few Ints.
Edge cases and common mistakes
K = 0. At time 0 the count is already 0, which is not below 0, so the loop doesn't run and the answer is 0.- Dividing the wrong way. The number of products is
time / t, nott / time. A worker with a slowtpacks few products. - Counting partial products. A worker with
t = 7has packed 4 products at time 29 and 4 products at time 30. The fifth product only counts at time 35. - Starting at time 1. Starting at 0 handles
K = 0without a special case. - Returning
productsinstead oftime. The function returns the time, not the product count. - Division by zero. A time of 0 per product would throw
ArithmeticExceptionintime / t. The problem assumes every time is positive.
Testing
times = [4, 7, 3, 6, 7, 1],K = 60gives 30.countProductsfor time 29 gives 57.times = [5],K = 3gives 15.times = [2, 3],K = 5gives 6.times = [4, 7, 3, 6, 7, 1],K = 0gives 0.