Minimum time to fulfil all orders

Geek is organizing a party at his house. For the party, he needs exactly n donuts for the guests. Geek decides to order the donuts from a nearby restaurant, which has l chefs and each chef has a rank r. A chef with rank r can make 1 donut in the first r minutes, 1 more donut in next 2r minutes, 1 more donut in 3r minutes, and so on. find the minimum time in which all the orders will be fulfilled.

Examples:

Input: n = 10, rank[] = [1, 2, 3, 4]
Output: 12
Explanation: Chef with rank 1, can make 4 donuts in time 1 + 2 + 3 + 4 = 10 mins
Chef with rank 2, can make 3 donuts in time 2 + 4 + 6 = 12 mins
Chef with rank 3, can make 2 donuts in time 3 + 6 = 9 mins
Chef with rank 4, can make 1 donuts in time = 4 minutes
Total donuts = 4 + 3 + 2 + 1 = 10 and 
Maximum time taken by all = 12 minutes.

Input: n = 8, rank[] = [1, 1, 1, 1, 1, 1, 1, 1]
Output: 1
Explanation: As all chefs are ranked 1, so each chef can make 1 donuts 1 min.
Total donuts = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 8 and  min time = 1 minute 

[Naive Approach] Using Linear Search

The idea is to use a brute-force linear search from time 1 up to Integer Maximum to check at each time point whether it is possible to make at least n donuts. At each time point, find the maximum number of donuts each chef can make and compare if the sum of donuts is greater than equal to n. The first time for which this is possible is considered the minimum time to fulfill the order.

#include <iostream>
#include <vector>
#include <climits>  

using namespace std;

// function to find if it is possible to make 
// atleast n donuts in timeAlloted time.
bool canMake(int n, vector<int> &rank, int timeAlloted) {
    int cnt = 0;
    int l = rank.size();
    
    for (int i = 0; i < l; i++) {
        int timeSpent = 0;
        int r = rank[i];
        
        // find the number of donuts i'th 
        // chef can make.
        while (timeSpent + r <= timeAlloted) {
            
            // Increment donut count 
            cnt++;
            
            timeSpent += r;
            r += rank[i];
        }
    }
    
    return cnt >= n;
}

// function to find Minimum time to fulfil all orders
int minTime(int n, vector<int>& rank) {
    
    int ans = -1;
    
    // Starting from 1 to Integer maximum
    for (int i = 1; i <= INT_MAX; i++) {
        
        // Check if it is possible to make 
        // n orders in i time, then this 
        // is the minimum time.
        if (canMake(n, rank, i)) {
            ans = i;
            break;
        }
    }
    
    return ans;
}

int main() {
    int n = 10;
    vector<int> rank = {1, 2, 3, 4};
    cout << minTime(n, rank);

    return 0;
}

class GfG {

    // Function to find if it is possible to make 
    // atleast n donuts in timeAlloted time.
    static boolean canMake(int n, int[] rank, int timeAlloted) {
        int cnt = 0;
        int l = rank.length;

        for (int i = 0; i < l; i++) {
            int timeSpent = 0;
            int r = rank[i];

            // Find the number of donuts i'th 
            // chef can make.
            while (timeSpent + r <= timeAlloted) {

                cnt++;

                timeSpent += r;
                r += rank[i];
            }
        }

        return cnt >= n;
    }

    // function to find Minimum time 
    // to fulfil all orders
    static int minTime(int n, int[] rank) {
        int ans = -1;

        //sStarting from 1 to Integer maximum
        for (int i = 1; i <= Integer.MAX_VALUE; i++) {

            // check if it is possible to make 
            // n orders in i time, then this 
            // is the minimum time.
            if (canMake(n, rank, i)) {
                ans = i;
                break;
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        int n = 10;
        int[] rank = {1, 2, 3, 4};
        System.out.println(minTime(n, rank));
    }
}

# Function to find if it is possible to make 
# atleast n donuts in timeAlloted time.
def canMake(n, rank, timeAlloted):
    cnt = 0
    l = len(rank)

    for i in range(l):
        timeSpent = 0
        r = rank[i]

        # Find the number of donuts i'th 
        # chef can make.
        while timeSpent + r <= timeAlloted:

            # Increment donut count 
            cnt += 1

            timeSpent += r
            r += rank[i]

    return cnt >= n

# Function to find Minimum time 
# to fulfil all orders
def minTime(n, rank):
    ans = -1

    # Starting from 1 to Integer maximum
    i = 1
    while i <= (2**31 - 1):

        # Check if it is possible to make 
        # n orders in i time, then this 
        # is the minimum time.
        if canMake(n, rank, i):
            ans = i
            break
        i += 1

    return ans

if __name__ == "__main__":
    n = 10
    rank = [1, 2, 3, 4]
    print(minTime(n, rank))

using System;

class GfG {

    // Function to find if it is possible to make 
    // atleast n donuts in timeAlloted time.
    static bool canMake(int n, int[] rank, int timeAlloted) {
        int cnt = 0;
        int l = rank.Length;

        for (int i = 0; i < l; i++) {
            int timeSpent = 0;
            int r = rank[i];

            // Find the number of donuts i'th 
            // chef can make.
            while (timeSpent + r <= timeAlloted) {

                // Increment donut count 
                cnt++;

                timeSpent += r;
                r += rank[i];
            }
        }

        return cnt >= n;
    }

    // Function to find Minimum time 
    // to fulfil all orders
    static int minTime(int n, int[] rank) {
        int ans = -1;

        // Starting from 1 to Integer maximum
        for (int i = 1; i <= int.MaxValue; i++) {

            // Check if it is possible to make 
            // n orders in i time, then this 
            // is the minimum time.
            if (canMake(n, rank, i)) {
                ans = i;
                break;
            }
        }

        return ans;
    }

    static void Main(string[] args) {
        int n = 10;
        int[] rank = {1, 2, 3, 4};
        Console.WriteLine(minTime(n, rank));
    }
}

// Function to find if it is possible to make 
// atleast n donuts in timeAlloted time.
function canMake(n, rank, timeAlloted) {
    let cnt = 0;
    const l = rank.length;

    for (let i = 0; i < l; i++) {
        let timeSpent = 0;
        let r = rank[i];

        // Find the number of donuts i'th 
        // chef can make.
        while (timeSpent + r <= timeAlloted) {

            // Increment donut count 
            cnt++;

            timeSpent += r;
            r += rank[i];
        }
    }

    return cnt >= n;
}

// Function to find Minimum time 
// to fulfil all orders
function minTime(n, rank) {
    let ans = -1;

    // Starting from 1 to Integer maximum
    for (let i = 1; i <= 2147483647; i++) {

        // Check if it is possible to make 
        // n orders in i time, then this 
        // is the minimum time.
        if (canMake(n, rank, i)) {
            ans = i;
            break;
        }
    }

    return ans;
}

// Driver Code
const n = 10;
const rank = [1, 2, 3, 4];
console.log(minTime(n, rank));

12

Time Complexity: O(t × l × sqrt(t)) where t is the maximum time iterated, l is the number of cooks. For each time point and each chef, the number of donuts k is found using 1 × r + 2 × r + 3 × r + ... + k × r <= timeAlloted. Maximum iterations will be sqrt(2 × timeAlloted / r)) which is roughly sqrt(timeAlloted).
Auxiliary Space: O(1)

[Better Approach] Using Binary Search and AP sum

The idea is to use binary search on the time to find the minimum time required to produce at least n donuts. For any given time, we calculate how many donuts each chef can make by summing the terms of an arithmetic progression where each chef takes r, 2r, 3r, ... seconds per donut, with r being the chef's rank. The total number of donuts made is the sum of such APs across all chefs. If the total meets or exceeds n, we try to minimize the time further; otherwise, we increase it. This combination of AP sum logic and binary search helps efficiently reach the answer.

Step by step approach:

• Each chef with rank r takes r seconds for the 1st donut, 2r for the 2nd, and so on.
  So, time to make k donuts is r × (1 + 2 + ... + k) = r × k × (k + 1) / 2.
• The minimum time can be 0, and the maximum time (upper bound) can be the time the fastest chef would take to make all n donuts alone.
  That’s given by: rmin × n × (n + 1) / 2 where rmin is the smallest rank.
• Perform binary search over time from 0 to rmin × n × (n + 1) / 2.
• For each mid time:
  compute how many donuts each chef can make using the quadratic formula derived from AP sum:
• k(k+1)/2 <= t/r → k = floor((-1 + sqrt(1 + 8t/r)) / 2)
  Sum these for all chefs.
  If total donuts ≥ n, update answer and try a smaller time (move left).
  Otherwise, try a larger time (move right).
• Return the Minimum Time Found:
  The binary search narrows down the minimum time required to fulfill all orders.

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

// returns number of donuts a chef with
// rank r can make in time t
int donutsByChef(int t, int r) {
    double D = 1.0 + 8.0 * t / r;
    return int((-1.0 + sqrt(D)) / 2.0);
}

// Checks if all chefs can make
// at least n donuts in time t
bool canMake(vector<int>& ranks, int n, int t) {
    int total = 0;
    for (int r : ranks) {
        total += donutsByChef(t, r);
        if (total >= n)
            return true;
    }
    return false;
}

// binary search on time to
// find minimum time needed
int minTime(vector<int>& ranks, int n) {
    int rmin = *min_element(ranks.begin(), ranks.end());
    int hi = rmin * n * (n + 1) / 2;
    int lo = 0, ans = hi;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (canMake(ranks, n, mid)) {
            ans = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    return ans;
}

int main() {
    int n = 10;
    vector<int> ranks = {1, 2, 3, 4};
    cout << minTime(ranks, n) << endl;
    return 0;
}

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

class GfG {

    // returns number of donuts a chef with
    // rank r can make in time t
    public static int donutsByChef(int t, int r) {
        double D = 1.0 + 8.0 * t / (double) r;
        return (int)((-1.0 + Math.sqrt(D)) / 2.0);
    }

    // Checks if all chefs can make at 
    // least n donuts in time t
    public static boolean canMake(int[] ranks, int n, int t) {
        int total = 0;
        for (int r : ranks) {
            total += donutsByChef(t, r);
            if (total >= n)
                return true;
        }
        return false;
    }

    // binary search on time to
    // find minimum time needed
    public static int minTime(int[] ranks, int n) {
        int rmin = ranks[0];
        for (int i = 1; i < ranks.length; i++) {
            if (ranks[i] < rmin) {
                rmin = ranks[i];
            }
        }

        int hi = rmin * n * (n + 1) / 2;
        int lo = 0, ans = hi;

        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (canMake(ranks, n, mid)) {
                ans = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) throws IOException {
        int n = 10;
        int[] ranks = {1, 2, 3, 4};
        System.out.println(minTime(ranks, n));
    }
}

import math

# returns number of donuts a chef with
# rank r can make in time t
def donutsByChef(t, r):
    D = 1.0 + 8.0 * t / r
    return int((-1.0 + math.sqrt(D)) / 2.0)

# Checks if all chefs can make at 
# least n donuts in time t
def canMake(ranks, n, t):
    total = 0
    for r in ranks:
        total += donutsByChef(t, r)
        if total >= n:
            return True
    return False

# binary search on time to
# find minimum time needed
def minTime(ranks, n):
    rmin = min(ranks)
    hi = rmin * n * (n + 1) // 2
    lo = 0
    ans = hi

    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if canMake(ranks, n, mid):
            ans = mid
            hi = mid - 1
        else:
            lo = mid + 1

    return ans

if __name__ == "__main__":
    n = 10
    ranks = [1, 2, 3, 4]
    print(minTime(ranks, n))

using System;

class GfG{
    // returns number of donuts a chef with
    // rank r can make in time t
    static int donutsByChef(int t, int r){
        double D = 1.0 + 8.0 * t / r;
        return (int)((-1.0 + Math.Sqrt(D)) / 2.0);
    }

    // Checks if all chefs can make at 
    // least n donuts in time t
    static bool canMake(int[] ranks, int n, int t){
        int total = 0;
        foreach (int r in ranks){
            total += donutsByChef(t, r);
            if (total >= n)
                return true;
        }
        return false;
    }

    // binary search on time to
    // find minimum time needed
    static int minTime(int[] ranks, int n){
        int rmin = int.MaxValue;
        foreach (int r in ranks){
            if (r < rmin) rmin = r;
        }

        int hi = rmin * n * (n + 1) / 2;
        int lo = 0;
        int ans = hi;

        while (lo <= hi){
            int mid = lo + (hi - lo) / 2;
            if (canMake(ranks, n, mid)){
                ans = mid;
                hi = mid - 1;
            }
            else{
                lo = mid + 1;
            }
        }

        return ans;
    }

    static void Main(string[] args){
        int n = 10;
        int[] ranks = { 1, 2, 3, 4 };
        Console.WriteLine(minTime(ranks, n));
    }
}

// returns number of donuts a chef with
// rank r can make in time t
function donutsByChef(t, r) {
    const D = 1.0 + 8.0 * t / r;
    return Math.floor((-1.0 + Math.sqrt(D)) / 2.0);
}

// Checks if all chefs can make at 
// least n donuts in time t
function canMake(ranks, n, t) {
    let total = 0;
    for (const r of ranks) {
        total += donutsByChef(t, r);
        if (total >= n) return true;
    }
    return false;
}

// binary search on time to
// find minimum time needed
function minTime(ranks, n) {
    let rmin = Math.min(...ranks);
    let hi = Math.floor(rmin * n * (n + 1) / 2);
    let lo = 0;
    let ans = hi;

    while (lo <= hi) {
        const mid = Math.floor(lo + (hi - lo) / 2);
        if (canMake(ranks, n, mid)) {
            ans = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }

    return ans;
}

// Driver code
const n = 10;
const ranks = [1, 2, 3, 4];
console.log(minTime(ranks, n));

12

Time Complexity: O(l × log(n)), where l is the length of ranks array, and n is the number of donuts to be made.
Auxiliary Space: O(1).