First thing first, here is the code:\n\n```python\nclass Solution:\n def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:\n def enough(num) -> bool:\n total = mid//a + mid//b + mid//c - mid//ab - mid//ac - mid//bc + mid//abc\n return total >= n\n\n ab = a * b // math.gcd(a, b)\n ac = a * c // math.gcd(a, c)\n bc = b * c // math.gcd(b, c)\n abc = a * bc // math.gcd(a, bc)\n left, right = 1, 10 ** 10\n while left < right:\n mid = left + (right - left) // 2\n if enough(mid):\n right = mid\n else:\n left = mid + 1\n return left\n```\n\nI have built a powerful generalized binary search template and used it to solve many problems easily. Below is the detailed and clear introduction to this template. I believe it will be worth your time :)\n\n****\n\n# Intro\n\nBinary Search is quite easy to understand conceptually. Basically, it splits the search space into two halves and only keep the half that probably has the search target and throw away the other half that would not possibly have the answer. In this manner, we reduce the search space to half the size at every step, until we find the target. Binary Search helps us reduce the search time from linear O(n) to logarithmic O(log n). But when it comes to implementation, it\'s rather difficult to write a bug-free code in just a few minutes. Some of the most common problems include:\n\n- When to exit the loop? Should we use `left < right` or `left <= right` as the while loop condition?\n- How to initialize the boundary variable `left` and `right`?\n- How to update the boundary? How to choose the appropriate combination from `left = mid `, `left = mid + 1` and `right = mid`, `right = mid - 1`?\n\nA rather common misunderstanding of binary search is that people often think this technique could only be used in simple scenario like "Given a sorted array, find a specific value in it". As a matter of fact, it can be applied to much more complicated situations.\n\nAfter a lot of practice in LeetCode, I\'ve made a powerful binary search template and solved many Hard problems by just slightly twisting this template. I\'ll share the template with you guys in this post. I don\'t want to just show off the code and leave. Most importantly, I want to share the logical thinking: how to apply this general template to all sorts of problems. Hopefully, after reading this post, people wouldn\'t be pissed off any more when LeetCoding, "Holy sh*t! This problem could be solved with binary search! Why didn\'t I think of that before!"\n\n\n\n****\n\n\n\n# Most Generalized Binary Search\n\nSuppose we have a search space. It could be an array, a range, etc. Usually it\'s sorted in ascend order. For most tasks, we can transform the requirement into the following generalized form:\n\n**Minimize k , s.t. condition(k) is True**\n\nThe following code is the most generalized binary search template:\n\n```python\ndef binary_search(array) -> int:\n def condition(value) -> bool:\n pass\n\n left, right = 0, len(array)\n while left < right:\n mid = left + (right - left) // 2\n if condition(mid):\n right = mid\n else:\n left = mid + 1\n return left\n```\n\nWhat\'s really nice of this template is that, for most of the binary search problems, we only need to modify three parts after copy-pasting this template, and never need to worry about corner cases and bugs in code any more:\n\n- Correctly initialize the boundary variables `left` and `right`. Only one rule: set up the boundary to **include all possible elements**;\n- Decide return value. Is it `return left` or `return left - 1`? Remember this: **after exiting the while loop, `left` is the minimal k\u200B satisfying the `condition ` function**;\n- Design the `condition` function. This is the most difficult and most beautiful part. Needs lots of practice.\n\nBelow I\'ll show you guys how to apply this powerful template to many LeetCode problems.\n\n\n\n****\n\n\n\n# Basic Application\n\n## [278. First Bad Version [Easy]](https://leetcode.com/problems/first-bad-version/)\n\nYou are a product manager and currently leading a team to develop a new product. Since each version is developed based on the previous version, all the versions after a bad version are also bad. Suppose you have `n` versions `[1, 2, ..., n]` and you want to find out the first bad one, which causes all the following ones to be bad. You are given an API `bool isBadVersion(version)` which will return whether `version` is bad.\n\n**Example:**\n\n```scala\nGiven n = 5, and version = 4 is the first bad version.\n\ncall isBadVersion(3) -> false\ncall isBadVersion(5) -> true\ncall isBadVersion(4) -> true\n\nThen 4 is the first bad version. \n```\n\nFirst, we initialize `left = 1` and `right = n` to include all possible values. Then we notice that we don\'t even need to design the `condition` function. It\'s already given by the `isBadVersion` API. Finding the first bad version is equivalent to finding the minimal k satisfying `isBadVersion(k) is True`. Our template can fit in very nicely:\n\n```python\nclass Solution:\n def firstBadVersion(self, n) -> int:\n left, right = 1, n\n while left < right:\n mid = left + (right - left) // 2\n if isBadVersion(mid):\n right = mid\n else:\n left = mid + 1\n return left\n```\n\n****\n\n\n\n## [69. Sqrt(x) [Easy]](https://leetcode.com/problems/sqrtx/)\n\nImplement `int sqrt(int x)`. Compute and return the square root of *x*, where *x* is guaranteed to be a non-negative integer. Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.\n\n**Example:**\n\n```scala\nInput: 4\nOutput: 2\n```\n\n```scala\nInput: 8\nOutput: 2\n```\n\nQuite an easy problem. We need to search for maximal k satisfying `k^2 <= x`, so we can easily come up with the solution:\n\n```python\ndef mySqrt(x: int) -> int:\n left, right = 0, x\n while left < right:\n mid = left + (right - left) // 2\n if mid * mid <= x:\n left = mid + 1\n else:\n right = mid\n return left - 1\n```\n\nThere\'s one thing I\'d like to point out. Remember I say that **we usually look for the minimal k value satisfying certain condition**? But in this problem we are searching for maximal k value instead. Feeling confused? Don\'t be. Actually, the maximal k satisfying `condition(k) is False` is just equal to the minimal k satisfying `condition(k) is True` minus one. This is why I mentioned earlier that we need to decide which value to return, `left` or `left - 1`.\n\n\n\n****\n\n\n\n## [35. Search Insert Position [Easy]](https://leetcode.com/problems/search-insert-position/)\n\nGiven a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array.\n\n**Example:**\n\n```scala\nInput: [1,3,5,6], 5\nOutput: 2\n```\n\n```scala\nInput: [1,3,5,6], 2\nOutput: 1\n```\n\nVery classic application of binary search. We are looking for the minimal k value satisfying `nums[k] >= target`, and we can just copy-paste our template. Notice that our solution is correct regardless of whether the input array `nums` has duplicates. Also notice that the input `target` might be larger than all elements in `nums` and therefore needs to placed at the end of the array. That\'s why we should initialize `right = len(nums)` instead of `right = len(nums) - 1`.\n\n```python\nclass Solution:\n def searchInsert(self, nums: List[int], target: int) -> int:\n left, right = 0, len(nums)\n while left < right:\n mid = left + (right - left) // 2\n if nums[mid] >= target:\n right = mid\n else:\n left = mid + 1\n return left\n```\n\n\n\n****\n\n\n\n# Advanced Application\n\nThe above problems are quite easy to solve, because they already give us the array to be searched. We\'d know that we should use binary search to solve them at first glance. However, more often are the situations where the search space and search target are not so readily available. Sometimes we won\'t even realize that the problem should be solved with binary search -- we might just turn to dynamic programming or DFS and get stuck for a very long time.\n\nAs for the question "When can we use binary search?", my answer is that, **If we can discover some kind of monotonicity, for example, if `condition(k) is True` then `condition(k + 1) is True`, then we can consider binary search**.\n\n## [1011. Capacity To Ship Packages Within D Days [Medium]](https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/)\n\ndays. The `i`-th package on the conveyor belt has a weight of `weights[i]`. Each day, we load the ship with packages on the conveyor belt (in the order given by `weights`). We may not load more weight than the maximum weight capacity of the ship. \n\nReturn the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within `D` days.\n\n**Example :**\n\n```scala\nInput: weights = [1,2,3,4,5,6,7,8,9,10], D = 5\nOutput: 15\nExplanation: \nA ship capacity of 15 is the minimum to ship all the packages in 5 days like this:\n1st day: 1, 2, 3, 4, 5\n2nd day: 6, 7\n3rd day: 8\n4th day: 9\n5th day: 10\n\nNote that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed. \n```\n\nBinary search probably would not come to our mind when we first meet this problem. We might automatically treat `weights` as search space and then realize we\'ve entered a dead end after wasting lots of time. In fact, we are looking for the minimal one among all feasible capacities. We dig out the monotonicity of this problem: if we can successfully ship all packages within `D` days with capacity `m`, then we can definitely ship them all with any capacity larger than `m`. Now we can design a `condition` function, let\'s call it `feasible`, given an input `capacity`, it returns whether it\'s possible to ship all packages within `D` days. This can run in a greedy way: if there\'s still room for the current package, we put this package onto the conveyor belt, otherwise we wait for the next day to place this package. If the total days needed exceeds `D`, we return `False`, otherwise we return `True`.\n\nNext, we need to initialize our boundary correctly. Obviously `capacity` should be at least `max(weights)`, otherwise the conveyor belt couldn\'t ship the heaviest package. On the other hand, `capacity` need not be more than`sum(weights)`, because then we can ship all packages in just one day.\n\nNow we\'ve got all we need to apply our binary search template:\n\n```python\ndef shipWithinDays(weights: List[int], D: int) -> int:\n def feasible(capacity) -> bool:\n days = 1\n total = 0\n for weight in weights:\n total += weight\n if total > capacity: # too heavy, wait for the next day\n total = weight\n days += 1\n if days > D: # cannot ship within D days\n return False\n return True\n\n left, right = max(weights), sum(weights)\n while left < right:\n mid = left + (right - left) // 2\n if feasible(mid):\n right = mid\n else:\n left = mid + 1\n return left\n```\n\n\n\n****\n\n\n\n## [410. Split Array Largest Sum [Hard]](https://leetcode.com/problems/split-array-largest-sum/)\n\nGiven an array which consists of non-negative integers and an integer *m*, you can split the array into *m* non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these *m* subarrays.\n\n**Example:**\n\n```scala\nInput:\nnums = [7,2,5,10,8]\nm = 2\n\nOutput:\n18\n\nExplanation:\nThere are four ways to split nums into two subarrays. The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18.\n```\n\nIf you take a close look, you would probably see how similar this problem is with LC 1011 above. Similarly, we can design a `feasible` function: given an input `threshold`, then decide if we can split the array into several subarrays such that every subarray-sum is less than or equal to `threshold`. In this way, we discover the monotonicity of the problem: if `feasible(m)` is `True`, then all inputs larger than `m` can satisfy `feasible` function. You can see that the solution code is exactly the same as LC 1011.\n\n```python\ndef splitArray(nums: List[int], m: int) -> int: \n def feasible(threshold) -> bool:\n count = 1\n total = 0\n for num in nums:\n total += num\n if total > threshold:\n total = num\n count += 1\n if count > m:\n return False\n return True\n\n left, right = max(nums), sum(nums)\n while left < right:\n mid = left + (right - left) // 2\n if feasible(mid):\n right = mid \n else:\n left = mid + 1\n return left\n```\n\nBut we probably would have doubts: It\'s true that `left` returned by our solution is the minimal value satisfying `feasible`, but how can we know that we can split the original array to **actually get this subarray-sum**? For example, let\'s say `nums = [7,2,5,10,8]` and `m = 2`. We have 4 different ways to split the array to get 4 different largest subarray-sum correspondingly: `25:[[7], [2,5,10,8]]`, `23:[[7,2], [5,10,8]]`, `18:[[7,2,5], [10,8]]`, `24:[[7,2,5,10], [8]]`. Only 4 values. But our search space `[max(nums), sum(nums)] = [10, 32]` has much more that just 4 values. That is, no matter how we split the input array, we cannot get most of the values in our search space.\n\nLet\'s say `k` is the minimal value satisfying `feasible` function. We can prove the correctness of our solution with proof by contradiction. Assume that no subarray\'s sum is equal to `k`, that is, every subarray sum is less than `k`. The variable `total` inside `feasible` function keeps track of the total weights of current load. If our assumption is correct, then `total` would always be less than `k`. As a result, `feasible(k - 1)` must be `True`, because `total` would at most be equal to `k - 1` and would never trigger the if-clause `if total > threshold`, therefore `feasible(k - 1)` must have the same output as `feasible(k)`, which is `True`. But we already know that `k` is the minimal value satisfying `feasible` function, so `feasible(k - 1)` has to be `False`, which is a contradiction. So our assumption is incorrect. Now we\'ve proved that our algorithm is correct.\n\n\n\n****\n\n\n\n## [875. Koko Eating Bananas [Medium]](https://leetcode.com/problems/koko-eating-bananas/)\n\nKoko loves to eat bananas. There are `N` piles of bananas, the `i`-th pile has `piles[i]` bananas. The guards have gone and will come back in `H` hours. Koko can decide her bananas-per-hour eating speed of `K`. Each hour, she chooses some pile of bananas, and eats K bananas from that pile. If the pile has less than `K` bananas, she eats all of them instead, and won\'t eat any more bananas during this hour. \n\nKoko likes to eat slowly, but still wants to finish eating all the bananas before the guards come back. **Return the minimum integer `K` such that she can eat all the bananas within `H` hours**.\n\n**Example :**\n\n```scala\nInput: piles = [3,6,7,11], H = 8\nOutput: 4\n```\n\n```scala\nInput: piles = [30,11,23,4,20], H = 5\nOutput: 30\n```\n\n```scala\nInput: piles = [30,11,23,4,20], H = 6\nOutput: 23\n```\n\nVery similar to LC 1011 and LC 410 mentioned above. Let\'s design a `feasible` function, given an input `speed`, determine whether Koko can finish all bananas within `H` hours with hourly eating speed `speed`. Obviously, the lower bound of the search space is 1, and upper bound is `max(piles)`, because Koko can only choose one pile of bananas to eat every hour.\n\n```python\ndef minEatingSpeed(piles: List[int], H: int) -> int:\n def feasible(speed) -> bool:\n # return sum(math.ceil(pile / speed) for pile in piles) <= H # slower \n return sum((pile - 1) / speed + 1 for pile in piles) <= H # faster\n\n left, right = 1, max(piles)\n while left < right:\n mid = left + (right - left) // 2\n if feasible(mid):\n right = mid\n else:\n left = mid + 1\n return left\n```\n\n\n\n****\n\n\n\n## [1482. Minimum Number of Days to Make m Bouquets [Medium]](https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/)\n\nGiven an integer array `bloomDay`, an integer `m` and an integer `k`. We need to make `m` bouquets. To make a bouquet, you need to use `k` **adjacent flowers** from the garden. The garden consists of `n` flowers, the `ith` flower will bloom in the `bloomDay[i]` and then can be used in **exactly one** bouquet. Return *the minimum number of days* you need to wait to be able to make `m` bouquets from the garden. If it is impossible to make `m` bouquets return **-1**.\n\n**Examples:**\n\n```scala\nInput: bloomDay = [1,10,3,10,2], m = 3, k = 1\nOutput: 3\nExplanation: Let\'s see what happened in the first three days. x means flower bloomed and _ means flower didn\'t bloom in the garden.\nWe need 3 bouquets each should contain 1 flower.\nAfter day 1: [x, _, _, _, _] // we can only make one bouquet.\nAfter day 2: [x, _, _, _, x] // we can only make two bouquets.\nAfter day 3: [x, _, x, _, x] // we can make 3 bouquets. The answer is 3.\n```\n\n```scala\nInput: bloomDay = [1,10,3,10,2], m = 3, k = 2\nOutput: -1\nExplanation: We need 3 bouquets each has 2 flowers, that means we need 6 flowers. We only have 5 flowers so it is impossible to get the needed bouquets and we return -1.\n```\n\nNow that we\'ve solved three advanced problems above, this one should be pretty easy to do. The monotonicity of this problem is very clear: if we can make `m` bouquets after waiting for `d` days, then we can definitely finish that as well if we wait more than `d` days.\n\n```python\ndef minDays(bloomDay: List[int], m: int, k: int) -> int:\n def feasible(days) -> bool:\n bonquets, flowers = 0, 0\n for bloom in bloomDay:\n if bloom > days:\n flowers = 0\n else:\n bonquets += (flowers + 1) // k\n flowers = (flowers + 1) % k\n return bonquets >= m\n\n if len(bloomDay) < m * k:\n return -1\n left, right = 1, max(bloomDay)\n while left < right:\n mid = left + (right - left) // 2\n if feasible(mid):\n right = mid\n else:\n left = mid + 1\n return left\n```\n\n\n\n****\n\n\n\n## [668. Kth Smallest Number in Multiplication Table [Hard]](https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/description/)\n\nNearly every one have used the [Multiplication Table](https://en.wikipedia.org/wiki/Multiplication_table). But could you find out the `k-th` smallest number quickly from the multiplication table? Given the height `m` and the length `n` of a `m * n` Multiplication Table, and a positive integer `k`, you need to return the `k-th` smallest number in this table.\n\n**Example :**\n\n```scala\nInput: m = 3, n = 3, k = 5\nOutput: 3\nExplanation: \nThe Multiplication Table:\n1\t2\t3\n2\t4\t6\n3\t6\t9\n\nThe 5-th smallest number is 3 (1, 2, 2, 3, 3).\n```\n\nFor Kth-Smallest problems like this, what comes to our mind first is Heap. Usually we can maintain a Min-Heap and just pop the top of the Heap for k times. However, that doesn\'t work out in this problem. We don\'t have every single number in the entire Multiplication Table, instead, we only have the height and the length of the table. If we are to apply Heap method, we need to explicitly calculate these `m * n` values and save them to a heap. The time complexity and space complexity of this process are both O(mn), which is quite inefficient. This is when binary search comes in. Remember we say that designing `condition` function is the most difficult part? In order to find the k-th smallest value in the table, we can design an `enough` function, given an input `num`, determine whether there\'re at least k values less than or equal to `num`. **The minimal `num` satisfying `enough` function is the answer we\'re looking for**. Recall that the key to binary search is discovering monotonicity. In this problem, if `num` satisfies `enough`, then of course any value larger than `num` can satisfy. This monotonicity is the fundament of our binary search algorithm.\n\nLet\'s consider search space. Obviously the lower bound should be 1, and the upper bound should be the largest value in the Multiplication Table, which is `m * n`, then we have search space `[1, m * n]`. The overwhelming advantage of binary search solution to heap solution is that it doesn\'t need to explicitly calculate all numbers in that table, all it needs is just picking up one value out of the search space and apply `enough` function to this value, to determine should we keep the left half or the right half of the search space. In this way, binary search solution only requires constant space complexity, much better than heap solution.\n\nNext let\'s consider how to implement `enough` function. It can be observed that every row in the Multiplication Table is just multiples of its index. For example, all numbers in 3rd row `[3,6,9,12,15...]` are multiples of 3. Therefore, we can just go row by row to count the total number of entries less than or equal to input `num`. Following is the complete solution.\n\n```python\ndef findKthNumber(m: int, n: int, k: int) -> int:\n def enough(num) -> bool:\n count = 0\n for val in range(1, m + 1): # count row by row\n add = min(num // val, n)\n if add == 0: # early exit\n break\n count += add\n return count >= k \n\n left, right = 1, n * m\n while left < right:\n mid = left + (right - left) // 2\n if enough(mid):\n right = mid\n else:\n left = mid + 1\n return left \n```\n\nIn LC 410 above, we have doubt "Is the result from binary search actually a subarray sum?". Here we have a similar doubt: "Is the result from binary search actually in the Multiplication Table?". The answer is yes, and we also can apply proof by contradiction. Denote `num` as the minimal input that satisfies `enough` function. Let\'s assume that `num` is not in the table, which means that `num` is not divisible by any `val` in `[1, m]`, that is, `num % val > 0`. Therefore, changing the input from `num` to `num - 1` doesn\'t have any effect on the expression `add = min(num // val, n)`. So `enough(num)` would also return `True`, just like `enough(num)`. But we already know `num` is the minimal input satisfying `enough` function, so `enough(num - 1)` has to be `False`. Contradiction! The opposite of our original assumption is true: `num` is actually in the table.\n\n\n\n****\n\n\n\n## [719. Find K-th Smallest Pair Distance [Hard]](https://leetcode.com/problems/find-k-th-smallest-pair-distance/)\n\nGiven an integer array, return the k-th smallest **distance** among all the pairs. The distance of a pair (A, B) is defined as the absolute difference between A and B.\n\n**Example :**\n\n```scala\nInput:\nnums = [1,3,1]\nk = 1\nOutput: 0 \nExplanation:\nFollowing are all the pairs. The 1st smallest distance pair is (1,1), and its distance is 0.\n(1,3) -> 2\n(1,1) -> 0\n(3,1) -> 2\n```\n\nVery similar to LC 668 above, both are about finding Kth-Smallest. Just like LC 668, We can design an `enough` function, given an input `distance`, determine whether there\'re at least k pairs whose distances are less than or equal to `distance`. We can sort the input array and use two pointers (fast pointer and slow pointer, pointed at a pair) to scan it. Both pointers go from leftmost end. If the current pair pointed at has a distance less than or equal to `distance`, all pairs between these pointers are valid (since the array is already sorted), we move forward the fast pointer. Otherwise, we move forward the slow pointer. By the time both pointers reach the rightmost end, we finish our scan and see if total counts exceed k. Here is the implementation:\n\n```python\ndef enough(distance) -> bool: # two pointers\n count, i, j = 0, 0, 0\n while i < n or j < n:\n while j < n and nums[j] - nums[i] <= distance: # move fast pointer\n j += 1\n count += j - i - 1 # count pairs\n i += 1 # move slow pointer\n return count >= k\n```\n\nObviously, our search space should be `[0, max(nums) - min(nums)]`. Now we are ready to copy-paste our template:\n\n```python\ndef smallestDistancePair(nums: List[int], k: int) -> int:\n nums.sort()\n n = len(nums)\n left, right = 0, nums[-1] - nums[0]\n while left < right:\n mid = left + (right - left) // 2\n if enough(mid):\n right = mid\n else:\n left = mid + 1\n return left\n```\n\n\n\n****\n\n\n\n## [1201. Ugly Number III [Medium]](https://leetcode.com/problems/ugly-number-iii/)\n\nWrite a program to find the `n`-th ugly number. Ugly numbers are **positive integers** which are divisible by `a` **or** `b` **or** `c`.\n\n**Example :**\n\n```scala\nInput: n = 3, a = 2, b = 3, c = 5\nOutput: 4\nExplanation: The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10... The 3rd is 4.\n```\n\n```scala\nInput: n = 4, a = 2, b = 3, c = 4\nOutput: 6\nExplanation: The ugly numbers are 2, 3, 4, 6, 8, 9, 10, 12... The 4th is 6.\n```\n\nNothing special. Still finding the Kth-Smallest. We need to design an `enough` function, given an input `num`, determine whether there are at least n ugly numbers less than or equal to `num`. Since `a` might be a multiple of `b` or `c`, or the other way round, we need the help of greatest common divisor to avoid counting duplicate numbers.\n\n```python\ndef nthUglyNumber(n: int, a: int, b: int, c: int) -> int:\n def enough(num) -> bool:\n total = mid//a + mid//b + mid//c - mid//ab - mid//ac - mid//bc + mid//abc\n return total >= n\n\n ab = a * b // math.gcd(a, b)\n ac = a * c // math.gcd(a, c)\n bc = b * c // math.gcd(b, c)\n abc = a * bc // math.gcd(a, bc)\n left, right = 1, 10 ** 10\n while left < right:\n mid = left + (right - left) // 2\n if enough(mid):\n right = mid\n else:\n left = mid + 1\n return left\n```\n\n\n\n****\n\n\n\n## [1283. Find the Smallest Divisor Given a Threshold [Medium]](https://leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/)\n\nGiven an array of integers `nums` and an integer `threshold`, we will choose a positive integer divisor and divide all the array by it and sum the result of the division. Find the **smallest** divisor such that the result mentioned above is less than or equal to `threshold`.\n\nEach result of division is rounded to the nearest integer greater than or equal to that element. (For example: 7/3 = 3 and 10/2 = 5). It is guaranteed that there will be an answer.\n\n**Example :**\n\n```scala\nInput: nums = [1,2,5,9], threshold = 6\nOutput: 5\nExplanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1. \nIf the divisor is 4 we can get a sum to 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2). \n```\n\nAfter so many problems introduced above, this one should be a piece of cake. We don\'t even need to bother to design a `condition` function, because the problem has already told us explicitly what condition we need to satisfy.\n\n```python\ndef smallestDivisor(nums: List[int], threshold: int) -> int:\n def condition(divisor) -> bool:\n return sum((num - 1) // divisor + 1 for num in nums) <= threshold\n\n left, right = 1, max(nums)\n while left < right:\n mid = left + (right - left) // 2\n if condition(mid):\n right = mid\n else:\n left = mid + 1\n return left\n```\n\n\n\n****\n\n\n\n# End\n\nWow, thank you so much for making it to the end, really appreciate that. As you can see from the python codes above, they all look very similar to each other. That\'s because I copy-pasted my template all the time. No exception. This is the strong proof of my template\'s powerfulness. I believe everyone can acquire this binary search template to solve many problems. All we need is just more practice to build up our ability to discover the monotonicity of the problem and to design a beautiful `condition` function.\n\nHope this helps.\n\n**Reference**\n\n- [[C++ / Fast / Very clear explanation / Clean Code] Solution with Greedy Algorithm and Binary Search](https://leetcode.com/problems/split-array-largest-sum/discuss/89819/C%2B%2B-Fast-Very-clear-explanation-Clean-Code-Solution-with-Greedy-Algorithm-and-Binary-Search)\n- [Approach the problem using the "trial and error" algorithm](https://leetcode.com/problems/find-k-th-smallest-pair-distance/discuss/109082/Approach-the-problem-using-the-"trial-and-error"-algorithm)\n- [Binary Search 101 The-Ultimate-Binary-Search-Handbook - LeetCode](https://leetcode.com/problems/binary-search/discuss/423162/Binary-Search-101-The-Ultimate-Binary-Search-Handbook)\n- [ugly-number-iii Binary Search with picture & Binary Search Template - LeetCode](https://leetcode.com/problems/ugly-number-iii/discuss/387539/cpp-Binary-Search-with-picture-and-Binary-Search-Template)\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n

Ugly Number III

Problem Description

Problem Description

Answer Panel