Mar 07, 2023
Edit me

#. Problem

Go to the problem on leetcode

1. My approach

Considering the constraints, time.length <= 10^5, totalTrips <= 10^5, brute force approach would not be possible.
I thought of using map with binary search but it didn’t work very well.
The main reason for this is that it needed slight changes of the binary search. Normally binary search would be like below.

int binary_search(arr, target){
    mid = (left + right) / 2;
    
    if(arr[mid] == target){
        return mid;
    } else if(arr[mid] < target){
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}

But in this problem, because of the constraints, it should be like below.

int binary_search(arr, target){
    mid = (left + right) / 2;
    
    if(arr[mid] == target){
        return mid;
    } else if(arr[mid] < target){
        left = mid + 1;
    } else {
        // This is the only difference.
        right = mid;
    }
}

So I tried it out, but I didn’t solve it due to time limit, which I am not sure why I am getting those. Myabe due to the Map structure? but it’d only take 1e5 at worst. 

function minimumTime(time: number[], totalTrips: number): number {
    const m = {};
    let left = 1, right = 1e5 * 1e7;
    time.forEach(el => m[el] = m[el]? m[el]+1:1);

    let currentTrips = 0;
    let mid = Math.floor((left + right)/2);

    while((currentTrips = getT(m, mid)) !== totalTrips){
        // console.log(left, right, mid, currentTrips);

        if(currentTrips > totalTrips){
            right = mid;
        } else {
            left = mid+1;
        }
        mid = Math.floor((left + right)/2);

        if(left >= right){
            // console.log('left >= right', left, right);
            return Math.max(left, right);
        }
    }

    while(currentTrips === getT(m, --mid));

    return mid+1;
};

const getT = (m: {}, currentTime: number): number => {
    let res = 0;
    for(const tripTime in m){
        const no = Number(tripTime)
        res += Math.floor(currentTime/no) * m[tripTime];
    }
    return res;
}

2. Solution

Solution is visible here, so I won’t be posting it here.
I will try to solve this once more when I almost forget about it.

3. Epilogue

What I’ve learned from this exercise:

  • tiny tweaks can make a huge difference.