Start learning free

LESSON 254 OF 348 · BINARY SEARCH

The Factory in Kotlin: O(n log(k * T)) with 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

    KOTLIN · BINARY SEARCH

    The Factory in Kotlin, explained

    Problem overview

    The function minTime receives an IntArray called times and an Int called K. Worker i needs times[i] units of time per product, and all workers pack at the same time. The function returns the smallest time in which they pack at least K products together.

    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, and in 29 units only 57.

    In time units a worker with time t per product packs time / t products, rounded down.

    Approach: binary search on the answer

    The brute-force way tries time 0, 1, 2 and so on until the workers reach K products. That works, but the answer can be huge. The statement's budget here is O(n * log(k * T)), which suggests a binary search over the possible times instead.

    The search is possible because the check is monotonic: if the workers can pack K products in some time, they can do it in any longer time too. Below the answer, every time gives fewer than K products. From the answer on, every time gives at least K. A binary search finds the boundary between the two groups.

    It needs a range to search. The lower end is 1. The upper end comes from the fastest worker, with time minValue: working alone, that worker packs K products in minValue * K units. The whole factory can't need more, so the answer is at most minValue * K.

    Each step looks at the middle time mid of the range and counts the products:

    • If the count is below K, mid is too short and so is everything below it, so the search continues in the upper half.
    • Otherwise mid is enough. It might be the answer, so it is recorded, and the search continues in the lower half for something shorter.

    With [4, 7, 3, 6, 7, 1] and K = 60, the fastest worker has minValue = 1, so the range is 1 to 60. The first middle is 30, which packs exactly 60, so 30 is recorded and the range becomes 1 to 29. The count for 15 is 3 + 2 + 5 + 2 + 2 + 15 = 29, too short, so the range moves up, and the search keeps narrowing until nothing below 30 is left. The recorded answer stays 30.

    Step by step

    1. Find the fastest worker. Start var minValue at times[0] and loop with for (t in times), updating it with minOf(minValue, t).
    2. Set the range. var left = 1 and var right = minValue * K, the smallest and largest times worth testing.
    3. Keep the best answer. var time = 0 will hold the smallest time found so far that packs at least K products.
    4. Loop while the range has candidates: left <= right.
    5. Take the middle, val mid = (left + right) / 2. Integer division drops the fraction.
    6. Test it. With the helper countProducts(times, mid), check whether the count is less than K. If so, set left = mid + 1.
    7. Else record and go lower. Set time = mid, then right = mid - 1. Record first: the loop can end on a mid that was too short, so the last good one must already be saved.
    8. Return time after the loop.
    9. Write the helper above minTime as fun countProducts(times: IntArray, time: Int): Int. It adds time / t to a running products for every t in times and returns the total.

    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 minValue = times[0]
        for (t in times) {
            minValue = minOf(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
            }
        }
        return time
    }
}

    The Kotlin details worth a closer look:

    • minOf. minOf(a, b) is a standard-library function that returns the smaller of two values, so no import is needed.
    • val mid inside the loop. A new val is created on each iteration, which is fine. Only left, right and time live across iterations, so only they are var.
    • Integer division. In time / t and (left + right) / 2, both operands are Int, so the fraction is dropped.
    • Int limits. Int holds up to 2147483647 and wraps silently past that. The bound minValue * K and the sum left + right must both fit.

    Complexity

    Time: O(n * log(k * T)). The range holds up to minValue * K candidate times, and every iteration halves it, so there are about log2(minValue * K) iterations. Each iteration calls countProducts, which is one pass over n workers. The initial scan for minValue adds O(n).

    Space: O(1). Only a few Int variables are used.

    Edge cases and common mistakes

    • Forgetting to record time. Returning left or mid after the loop is wrong when the final probe was too short. Saving mid in the else branch avoids it.
    • K = 0. The range is 1 to 0, so the loop never runs and the function returns 0.
    • One worker. For times = [5] and K = 3, the range is 1 to 15 and the answer is 15.
    • Discarding the wrong half. Too few products means the time is too short: go up with left = mid + 1. Searching down there never reaches the answer.
    • Overflow. If minValue * K is larger than 2147483647, the product wraps around to a wrong bound. For times = [3] and K = 1000000000, the function returns 0 instead of 3000000000. The lesson's tests stay within Int, but a larger problem would need Long.
    • Starting the range at 0. It works for K at least 1 but wastes a step, since 0 time packs nothing.

    Testing

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