thảo luận Leetcode mỗi ngày

class Solution:
    def maxDistance(self, p: List[int], m: int) -> int:
        p.sort()
        l = 1
        r = p[-1] - p[0]
        def can_put_the_balls(f):
            count = 1
            last_pos = p[0]
            for i in range(1, len(p)):
                if p[i] - last_pos >= f:
                    count += 1
                    last_pos = p[i]
                    if count == m:
                        return True
            return False
        ans = 0
        while l <= r:
            mid = l + (r - l) // 2
            if can_put_the_balls(mid):
                l = mid + 1
                ans = mid
            else:
                r = mid - 1
                
        return ans

class Solution {
    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        int n = position.length;
        int left = 1;
        int right = position[n - 1] - position[0];
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (condition(position, m, mid)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    boolean condition(int[] pos, int m, int range){
        int n = pos.length;
        int last_pos = 0;
        int cnt=1;
        for(int i = 1; i<n;i++){
            if(pos[i]-pos[last_pos]>range){
                last_pos = i;
                cnt++;
            }
            if(cnt==m) return true;
        }
        return false;
    }
}

class Solution {
public:
    int maxDistance(vector<int>& pos, int m) {
        sort(begin(pos), end(pos));
        if (m == 2) return pos.back() - pos[0];
        int n = pos.size(), lo = 1, hi = pos[n - 1] - pos[0];
        function<bool(int)> solve = [&](int dis) -> bool {
            int cnt = 1, i = 0;
            while (cnt < m) {
                i = lower_bound(begin(pos) + i, end(pos), dis + pos[i]) - begin(pos);
                if (i == n) break;
                cnt++;
            }
            return cnt >= m;
        };
        while (lo < hi) {
            int mi = (lo + hi) / 2;
            if (solve(mi)) lo = mi + 1;
            else hi = mi;
        }
        return lo - 1;
    }
};

// Problem: https://leetcode.com/problems/magnetic-force-between-two-balls/
class Solution {
    func maxDistance(_ position: [Int], _ m: Int) -> Int {
        let sortedPos = position.sorted()
        let len = position.count

        func validate(_ value: Int) -> Bool {
            var cnt = 1
            var next = 1
            var currentPos = sortedPos[0]

            while (next < len) {
                if currentPos + value <= sortedPos[next] {
                    // nếu có position tiếp theo
                    currentPos = sortedPos[next]
                    next += 1
                    cnt += 1
                } else {
                    next += 1
                }

                if cnt == m {
                    return true
                }
            }
            return false
        }

        // value min is 1, max is last-first
        var left: Int = 1
        var right: Int = sortedPos[len-1] - sortedPos[0]
        var ans: Int = 0
        while (left <= right) {
            let mid: Int = (left + right)/2
            if (validate(mid)) {
                ans = max(ans, mid)
                left = mid + 1
            } else {
                // search in just case (left, mid-1)
                right = mid - 1
            }
        }
       
        return ans
    }
}

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def check(minDistance):
            balls = 0
            prev = -math.inf
            for pos in position:
                if pos - prev >= minDistance:
                    balls += 1
                    if balls == m:
                        return True
                    prev = pos
            return False

        position.sort()
        lo = 1
        hi = (position[-1] - position[0] + 1) // (m - 1)
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if check(mid):
                lo = mid
            else:
                hi = mid - 1
        return lo

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def check(minDistance):
            balls = 0
            prev = -math.inf
            for pos in position:
                if pos - prev >= minDistance:
                    balls += 1
                    if balls == m:
                        return True
                    prev = pos
            return False

        position.sort()
        lo = 1
        hi = (position[-1] - position[0] + 1) // (m - 1)
        searchRange = range(hi, lo - 1, -1)
        return searchRange[bisect.bisect_left(searchRange, x=True, key=check)]