Binary Search

Numbers At Most N Given Digit Set - LeetCode

When the length of candidates are less than length of str(N) is simple.
For the case of length of candidates == len(str(N)),
solve it by different cases and for the most complicated one, using binary search to get the answer.
for binary search part.
if D = {1,2,3}
and N = 230
then we can have the transition of
binary(3, 230) = res from (3 digits <200) + binary(2, 230–200) = 3² + res from (2 digits < 30) + binary(1, 30–20) = 3²+2*3¹+len{}

res from 2* + binary(1, 30–20) have valid numbers of {11, 12, 13, 21, 22, 23}

class Solution:
    def atMostNGivenDigitSet(self, D: List[str], N: int) -> int:
        def binary(n, L):
            if n==1:return  sum(int(d)<=L for d in D)
            l, r = 0, len(D)-1
            while l<r:
                m = (l+r+1)//2
                if int(D[m]+'0'*(n-1))<=L:l = m
                else:r = m-1
            return l*(len(D))**(n-1) + binary(n-1, L-int(D[l]+'0'*(n-1)))
        res = sum(len(D)**n for n in range(1, len(str(N))))
        min_ = int(D[0]*len(str(N)))
        if min_ < N:res += binary(len(str(N)), N)
        elif min_ == N:res += 1
        # min_ > N is not needed to condider.
        return res

878. Nth Magical Number

Nth Magical Number - LeetCode

class Solution:
    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
        a, b = A, B
        while b: a, b = b, a % b
        l, r, lcm = 2, 10**14, A * B // a
        while l < r:
            m = (l + r) // 2
            if m // A + m // B - m // lcm < N: l = m + 1
            else: r = m
        return l % (10**9 + 7)

875. Koko Eating Bananas

class Solution:
    def minEatingSpeed(self, piles: List[int], H: int) -> int:
        def good(m):
            return sum(math.ceil(p/m) for p in piles)<=H
        def binary():
            S = sum(piles)
            if H>=S:return 1
            l, r = 0, S
            while l<r:
                m = (l+r)//2
                if good(m):
                    r = m
                else:
                    l = m+1
            return l
        return binary()

1300. Sum of Mutated Array Closest to Target

https://leetcode.com/problems/sum-of-mutated-array-closest-to-target/

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        if sum(arr)==target:return max(arr)
        if len(arr)==1:return min(target, arr[0])
        arr.sort()
        cusum = list(itertools.accumulate([0]+arr))
        def good(m):
            idx = bisect.bisect(arr, m)
            if idx==len(arr):
                return cusum[-1]-target
            else:
                return target-cusum[idx]-(len(arr)-idx)*m
        def binary():
            l, r = target//len(arr), max(arr)
            heap = []
            heapq.heapify(heap)
            while l<=r:
                m = (l+r)//2
                d1, d2 = good(m), good(m+1) 
                heapq.heappush(heap, (abs(d1), m))
                heapq.heappush(heap, (abs(d2), m+1))
                if d1>0 and d2>0:
                    if d1<d2:
                        r = m
                    else:
                        l = m+1
                elif d1<0 and d2<0:
                    if d1>d2:
                        r = m
                    else:
                        l = m+1
                else:break
            return heap[0][1] if heap else l
        return binary()