Start learning free

LESSON 254 OF 348 · BINARY SEARCH

The Factory in TypeScript: O(n log(k*T)) Binary Search on the Answer

Practice O(n * log(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 * log(k * T)) time and use O(1) extra space.


STEP 1 OF 13
    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. They all work at once. The method minTime returns the smallest time in which they pack at least K products together.

    In the example, times = [4, 7, 3, 6, 7, 1] and K = 60. In 30 units the workers pack 7 + 4 + 10 + 5 + 4 + 30 = 60 products. In 29 units they pack only 57. The answer is 30.

    The statement asks for O(n * log(k * T)) time and O(1) extra space, where T is the time of the fastest worker.

    Approach: binary search on the answer

    A worker who needs t units per product packs Math.floor(time / t) products in time units. Summing that over the workers gives the total for a given time, and the total never decreases as time grows. So the times split into two groups: the short ones, which pack fewer than K products, and the long ones, which pack at least K. The answer is the first time of the second group.

    Checking one time costs O(n). The simple approach in the previous lesson checks 0, 1, 2, ... in turn. Because the groups are ordered, binary search can find the boundary instead, by checking the middle time and discarding half of the range.

    The search needs a range to start from:

    • The lower end is 1, since 0 units pack nothing.
    • The upper end is minValue * K, where minValue is the smallest entry of times. The fastest worker alone packs K products in that time, so the answer can't be larger.

    For times = [2, 3] and K = 5 the range is 1 to 10. The middle is 5, which packs 2 + 1 = 3 products, too few, so the search moves to 6 to 10. The middle is 8, which packs 4 + 2 = 6, enough, so it is recorded and the search moves to 6 to 7. The middle is 6, which packs 3 + 2 = 5, enough, so 6 is recorded and the range becomes 6 to 5, which is empty. The answer is 6.

    Step by step

    1. Find the fastest worker. Start minValue at times[0] and, with a for...of loop, update it with Math.min(minValue, t).
    2. Set the range. Declare left and right in one let, as 1 and minValue * K.
    3. Prepare the answer. Declare time as 0. It will hold the smallest time found so far that works.
    4. Loop while left <= right.
    5. Take the middle as const mid = Math.floor((left + right) / 2).
    6. If this.countProducts(times, mid) < K, the time is too short, so set left = mid + 1.
    7. Otherwise the time is enough. Record it with time = mid, then look for something shorter with right = mid - 1. Recording first matters: the loop may end on a time that was too short, and the last good one must already be saved.
    8. Return time.
    9. Write the helper countProducts(times: number[], time: number): number above minTime.
    10. Start products at 0, loop with for (const t of times) and add Math.floor(time / t) for each worker.
    11. 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 minValue = times[0];
        for (const t of times) {
            minValue = Math.min(minValue, t);
        }

        let left = 1, right = minValue * K;
        let time = 0;
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (this.countProducts(times, mid) < K) {
                left = mid + 1;
            } else {
                time = mid;
                right = mid - 1;
            }
        }
        return time;
    }
}

    Some TypeScript details:

    • Division keeps the fraction. number is a double, so 29 / 7 is about 4.14. Math.floor turns it into the 4 whole products.
    • Several variables in one let. let left = 1, right = minValue * K; declares both, each with its own initial value.
    • const for mid. Every iteration creates a new mid, so it never needs to be reassigned.
    • Large values are safe. The upper bound minValue * K is a double, and it stays exact up to 2^53, about 9 quadrillion. Sums and midpoints cannot overflow like a 32-bit integer in other languages.
    • Methods through this. countProducts belongs to the class, so the call is this.countProducts.

    Complexity

    Time: O(n * log(k * T)). The range holds about minValue * K times, and each loop pass halves it, so there are about log(minValue * K) passes. Each pass calls countProducts, which costs O(n). Finding minValue is one extra O(n) pass. With K equal to a billion and a fastest worker who needs 1 unit, the search takes about 30 passes, where the one-unit-at-a-time version needs up to a billion.

    Space: O(1). A few numbers, whatever the input size.

    Edge cases and common mistakes

    • Not saving the good time. If the answer is not recorded in the else branch, the loop ends with no record of the last time that worked. Saving mid there removes any off-by-one question at the end.
    • Upper bound too small. A bound below the true answer makes the search return 0. The fastest worker alone always meets K at minValue * K, so that bound is safe.
    • One worker. For times = [5] and K = 3 the range is 1 to 15, and the result is 15.
    • Using <= instead of < in the check. Then exactly K products would count as too few, and the answer would come out too long.
    • Forgetting Math.floor in countProducts. Fractions of a product would be counted.
    • Using / for the midpoint without rounding. A fractional mid would be tested and could be saved as the answer, such as 29.5.

    Testing

    • times = [4, 7, 3, 6, 7, 1], K = 60 gives 30.
    • times = [2, 3], K = 5 gives 6.
    • times = [5], K = 3 gives 15.
    • times = [4, 7, 3, 6, 7, 1], K = 1 gives 1.
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free