Start learning free

LESSON 253 OF 348 · BINARY SEARCH

The Factory in TypeScript: Counting Time Unit by Unit

Practice O(n * k * T) Read the full explanation

There are N workers in a factory. Each worker packs the same type of product, and for each of them we know the time it takes them to pack one product.

Find out the minimum amount of time the workers need to pack at least K products.

Example:

Input: times = [4, 7, 3, 6, 7, 1], K = 60
Output:30
Explanation:
1st worker packs 7 products in 4 * 7 = 28 units of time
2nd worker packs 4 products in 7 * 4 = 28 units of time
3rd worker packs 10 products in 3 * 10 = 30 units of time
4th worker packs 5 products in 6 * 5 = 30 units of time
5th worker packs 4 products in 7 * 4 = 28 units of time
6th worker packs 30 products in 1 * 30 = 30 units of time
We have 7 + 4 + 10 + 5 + 4 + 30 = 60 total products
in max(28, 28, 30, 30, 28, 30) = 30 units of time
and this is the minimum amount of time
since in 29 units of time we can pack only
7 + 4 + 9 + 4 + 4 + 29 = 57 products

Note:

Your algorithm should run in O(n * k * T) time and use O(1) extra space.


STEP 1 OF 9
    Ctrl + Enter to check

    TYPESCRIPT · BINARY SEARCH

    The Factory in TypeScript, explained

    Problem overview

    A factory has workers, and times[i] is the number of time units worker i needs to pack one product. All workers work at the same time. The method minTime returns the smallest amount of time in which the workers together pack at least K products.

    In the example, times = [4, 7, 3, 6, 7, 1] and K = 60. 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 and 29, which is 57, not enough. So the answer is 30.

    Approach: try 0, 1, 2, ... until it is enough

    A worker who needs t units per product packs Math.floor(time / t) products in time units: only whole products count. Add that up for all workers and you get the total for a given time.

    That total never goes down when time grows, because more time can't pack fewer products. So the answer is the first time at which the total reaches K. The simplest way to find it is to start at 0 and add one unit at a time until the total is big enough. The statement allows O(n * k * T) time for this lesson, which describes exactly this slow search: a check that costs n per time value, repeated up to as many times as the answer. A later lesson on the same problem replaces the counting with a binary search on the time.

    A short trace with times = [2, 3] and K = 5 shows the loop at work. At time 4 the workers pack 2 and 1 products, which is 3. At time 5 it is 2 and 1, still 3. At time 6 it is 3 and 2, which is 5, so the loop stops and the method returns 6. Time 5 gave no progress because neither worker finished another product in that unit, which is normal: the total only grows at some times, and the loop simply keeps going.

    Step by step

    1. Start the clock. Declare time with let and set it to 0.
    2. Loop while the total is too small. The loop condition is this.countProducts(times, time) < K. Writing it first, with the helper still to come, keeps the idea separate from the details.
    3. Add one unit with time++ in the loop body.
    4. Return time. The loop stops at the first time with at least K products.
    5. Declare the helper above minTime: countProducts(times: number[], time: number): number.
    6. Start a counter, products, at 0.
    7. Loop over the workers with for (const t of times).
    8. Add Math.floor(time / t) to products. Division on numbers keeps the fraction, so the rounding down is what leaves only whole products.
    9. Return products.

    The solution in TypeScript

    class Solution {
    countProducts(times: number[], time: number): number {
        let products = 0;
        for (const t of times) {
            products += Math.floor(time / t);
        }
        return products;
    }

    minTime(times: number[], K: number): number {
        let time = 0;
        while (this.countProducts(times, time) < K) {
            time++;
        }
        return time;
    }
}

    Some TypeScript details:

    • No integer division operator. 7 / 4 is 1.75, because number is a double. Math.floor(7 / 4) is 1. For non-negative values Math.trunc gives the same result.
    • for...of gives values, not indices. for (const t of times) binds t to each element. for...in would give the indices as strings, which is a classic mix-up.
    • const inside the loop. A new t is created on each iteration, so const is fine.
    • Calls go through this. countProducts is a method of the class, so minTime calls this.countProducts.

    Complexity

    Time: O(n * T), where n is the number of workers and T is the answer. Each pass of the loop calls countProducts, which visits all n workers, and the loop runs T + 1 times. The answer can be as large as the fastest worker's time multiplied by K, which is why the statement's bound mentions k and T.

    Space: O(1). Only a few numbers are kept.

    Edge cases and common mistakes

    • Forgetting to round down. Without Math.floor, a worker who needs 7 units would count as having packed 0.57 of a product after 4 units, and the total would reach K too early.
    • One worker. With times = [5] and K = 3 the answer is 15, the time for three products.
    • The loop starts at 0. With K = 0 the first check, 0 products against 0, is not less than K, so the method returns 0.
    • Large K with slow workers. The loop does as many passes as the answer, so a big answer is slow. This is the reason for the faster approach.
    • Splitting K among the workers. The workers all use the same amount of time, and each packs as many products as fit in it. Dividing K into shares is not part of the task.

    Testing

    • times = [4, 7, 3, 6, 7, 1], K = 60 gives 30.
    • The same workers with K = 1 give 1, because the fastest worker packs one product in 1 unit.
    • times = [5], K = 3 gives 15.
    • times = [2, 3], K = 5 gives 6: 3 products from the first worker and 2 from the second.
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free