Problem overview
The function minTime receives a slice times, where times[i] is how many units of time worker i needs to pack one product, and a number k. All workers pack at the same time. The function returns the smallest amount of time after which the workers have packed at least k products in total.
In the example, times = [4, 7, 3, 6, 7, 1] and k = 60. In 30 units of time the workers pack 7, 4, 10, 5, 4 and 30 products, which is exactly 60. In 29 units they pack only 7 + 4 + 9 + 4 + 4 + 29 = 57. So the answer is 30.
The statement allows O(N * K * T) time, where N is the number of workers and T is the smallest value in times, and O(1) extra space.
Approach: try 0, 1, 2, ... units of time
A worker who needs x units per product finishes t / x products (rounded down) in t units of time, because only complete products count. Adding this up over all workers gives the total for a given t.
That total never decreases as t grows: more time can only mean the same number of products or more. This is what makes a simple search correct. Start at t = 0 and increase it by one until the total reaches k. The first t that works is the smallest, because every smaller value was tried and failed.
How long can the loop run? The fastest worker, whose time per product is T, alone packs k products in T * k units. So the answer is at most T * k, and the loop makes at most T * k + 1 checks. Each check adds up N numbers, which gives the O(N * K * T) bound from the statement.
This is slow when the answer is large, but it is simple and obviously correct. Because the total only goes up with t, the search can be done with binary search on the answer instead of one step at a time. The second lesson on this problem does that.
Step by step
- Declare the time to try.
t := 0is the candidate answer. It is namedtbecausetimeis the name of a standard library package. - Loop while the workers are too slow.
for countProducts(times, t) < kkeeps going as long astunits are not enough. The helper doesn't exist yet; assuming it lets you write the main logic first. - Try one more unit.
t++inside the loop. - Return
t. When the loop stops,tis the first time for which the total reachedk. - Declare the helper.
countProducts(times []int, t int) intreturns the total aftertunits. - Start a total.
products := 0. - Loop over the workers.
for _, x := range timesgives each worker's time per product asx. The blank identifier_discards the index, which isn't needed. - Add one worker's products.
products += t / x. Dividing two integers in Go already drops the fraction, which is exactly "complete products only". - Return the total.
The solution in Go
func countProducts(times []int, t int) int {
products := 0
for _, x := range times {
products += t / x
}
return products
}
func minTime(times []int, k int) int {
t := 0
for countProducts(times, t) < k {
t++
}
return t
}
The Go details worth knowing:
- Integer division truncates. With both operands of type
int,t / xis the integer part of the quotient. A worker withx = 7packs29 / 7 = 4products in 29 units and30 / 7 = 4in 30. This is the reason the answer can be larger than the exact fractional answer. - Division by zero panics. If some value in
timeswere 0, the expressiont / xwould stop the program with a run-time panic. The lesson's workers always need at least one unit per product. foras awhile.for countProducts(times, t) < k { t++ }has only a condition. Go has nowhilekeyword. The condition is re-evaluated before every pass, so the body runs zero times if the first check already succeeds.rangeover a slice. It yields an index and a value. Go won't compile an unused variable, so the index is named_when you don't need it.- Slices are cheap to pass.
timesis passed to the helper as a small header pointing at the same data. Nothing is copied, and the helper only reads it.
Complexity
Time: O(N * K * T). One call to countProducts takes O(N). The loop calls it for t = 0, 1, 2, ... up to the answer, which is at most T * K. Multiplying gives N * K * T.
Space: O(1). Two integers in minTime and two in the helper. Nothing grows with the input.
Edge cases and common mistakes
- One worker. With
times = [5]andk = 3the answer is 15: att = 14the worker has packed 2 products, at 15 they have packed 3. Withk = 1it is 5. k = 0. Zero products are packed already att = 0, so the loop never runs and the function returns 0.- Exactly at a boundary. The condition is
< k, not<= k. "At leastk" means a total equal tokis enough to stop. With<=the loop would overshoot by one unit. - Leftover time is wasted. In the example, 29 units give the 7-unit worker only 4 products, with 1 unit unused. The sum is exact only when time divides evenly, so you can't compute the answer as
kdivided by the total speed. - Different workers finish different counts. The answer isn't the average of anything. Each worker is counted separately and the totals are added.
- Huge answers. With
times = [1000000]andk = 100, the answer is 100000000. The loop runs a hundred million times, which is the reason a faster search matters when the numbers are large.
Testing
times = [4, 7, 3, 6, 7, 1],k = 60gives 30.times = [2, 3],k = 5gives 6: att = 6the workers pack 3 + 2 = 5.times = [5],k = 3gives 15.times = [4, 4, 4],k = 0gives 0.
The helper alone is also easy to probe: countProducts([]int{2, 3}, t) returns 0, 0, 1, 2, 3 for t from 0 to 4.
