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

  • 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;
}