We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Minimum Time Required
  2. Discussions

Minimum Time Required

Sort by

recency

|

153 Discussions

|

  • sonali9696
     + 0 comments

    why is this TLE? I am using binary search and the last for loop -- couldn't possibly go too much back.

    long minTime(vector<long> machines, long goal) {
    //binary search
    // check if sum of machines = goal or < or >
    
    int n = machines.size();
    long fastest = *min_element(machines.begin(), machines.end());
    
    long low = 0, high = goal*fastest;
    long mid = (low+high)/2;
    long sum = 0;
    while(high >= low)
    {
        sum = 0;
        for(int i=0; i<n; i++)
        {
            sum += (mid/machines[i]);
        }
        
        if(sum == goal) break;
        else if(sum > goal)
        {
            high = mid;
        }
        else {
            low = mid;
        }
        mid = (low+high)/2;
    }
    
    int num = mid;
    while(sum == goal)
    {
        num--;
        sum = 0;
        for(int i=0; i<n; i++)
        {
            sum += (num/machines[i]);
        }
        if(sum != goal)
        {
            num++;
            break;
        }
    }
    return num;
}

  • bpirvali
     + 0 comments

    The binary search is certainly a great idea, but solutions I see all start from 0 or 1. The minum days is fastest-machine/number-of-machines * item_targets and the maxium days is slowest-machine/number-of-machines * item_targets:

    def min_time(machines, num_items_goal):
    fastest_machine = min(machines)
    slowest_machine = max(machines)
    fastest_production_num_days_per_item = fastest_machine // len(machines)
    slowest_production_num_days_per_item = slowest_machine // len(machines) + 1
    min_days, max_days = \
        fastest_production_num_days_per_item * num_items_goal, \
        slowest_production_num_days_per_item * num_items_goal
    while max_days - min_days > 1:
        mid = (max_days + min_days) // 2
        item_cnt = 0
        for m in machines:
            item_cnt += mid // m
        if item_cnt < num_items_goal:
            min_days = mid
        else:
            max_days = mid
    return max_days  # we return the bigger number

  • cherrymeteor
     + 0 comments

    JS binary search

    function minTime(machines, goal) {
  let min = 1, max = goal * Math.max(...machines)

  while (min < max) {
    let mid = parseInt((min + max) / 2)
    let prod = machines.reduce((prev, curr) => prev + parseInt(mid / curr), 0)
    if (prod < goal) min = mid + 1
    else max = mid
  }
  return min
}

  • IchbinJasmin
     + 0 comments

    JS Solution

    If minDays += 1 instead of minDays = midDays + 1 is used, the time complexity would exceed the limit. Can anyone explain why?

    function minTime(machines, goal) {
  let minDays = 0;
  let maxDays = Math.max(...machines) * goal;

  while (minDays < maxDays) { 
    let midDays = Math.floor((minDays + maxDays) / 2);
    let totalItems = 0;

    for (let machine of machines) {
      totalItems += Math.floor(midDays / machine);
    }

    if (totalItems < goal) {
      minDays = midDays + 1;
    } else {
      maxDays = midDays;
    }
  }
  return minDays;
}

// console.log(minTime([2, 3, 2], 10)); // 8
// console.log(minTime([2, 3], 5)); // 6
// console.log(minTime([1, 3, 4], 10)); // 7
// console.log(minTime([4, 5, 6], 12)); // 20

  • angelduarte
     + 0 comments

    this is my solution, it's a bit complicated but it works =).

    def minTime(machines, goal):
    sum_mach = sum(1/x for x in machines)
    days = [1, int(goal/sum_mach)]      
    n = 1
    print(days[-1])
    while True:               
        sum_prod = sum(days[-1]//x for x in machines)
        prom = ((goal-sum_prod)/2)**n;   
        min_mac = min([x - (days[-1] % x) for x in machines]) * prom
        if sum_prod >= goal:
            if prom == 1:
                break 
            else:
                days[-1] = days[-2]
                n = 0                     
        else: 
            days.append(days[-1]+min_mac)            
        print(prom, sum_prod)        
    return(int(days[-1]))