23.07.27 Today’s Leetcode

2226. Maximum Candies Allocated to K Children

TLE at 50/100

class Solution:
    def maximumCandies(self, candies: List[int], k: int) -> int:
        counter = Counter(candies)
        a, b = min(counter.keys()), max(counter.keys())
        d = defaultdict(int)
        cur = 0
        for i in range(b, -1, -1):
            cur += counter[i]
            d[i] = cur

        for i in range(b, 0, -1):
            temp = 0
            for j in range(1, b // i + 1):
                # print(d[i * j])
                temp += d[i * j]
            # print(i, temp)
            if temp >= k:
                return i
        
        return 0

Binary Search

class Solution:
    def maximumCandies(self, A, k):
        left, right = 0, sum(A) // k
        while left < right:
            mid = (left + right + 1) // 2
            if k > sum(a // mid for a in A):
                right = mid - 1
            else:
                left = mid
        return int(left)

2141. Maximum Running Time of N Computers (hard)

Binary Search, Again

class Solution:
    def maxRunTime(self, n: int, batteries: List[int]) -> int:
        left, right = 1, sum(batteries) // n 
        while left < right: 
            target = right - (right - left) // 2 
            if sum(min(battery, target) for battery in batteries) >= target * n: 
                left = target 
            else: 
                right = target - 1 
        return left