Binary Search
90% of the article here was copied from the leetcode discussion (Except for the last section Tips from a Smart Friend (!!!Recommend to read this first!!!) and the C++ Code I added when trying to solve the problem again). I found it super helpful and decided to publish a note on it in case the post gets deleted next time or I cannot find it again.
>> Intro
Binary 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:
- When to exit the loop? Should we use
left < rightorleft <= rightas the while loop condition? - How to initialize the boundary variable
leftandright? - How to update the boundary? How to choose the appropriate combination from
left = mid,left = mid + 1andright = mid,right = mid - 1?
A 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.
After 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, “This problem could be solved with binary search! Why didn’t I think of that before!”
>> Most Generalized Binary Search
Suppose we have a search space. It could be an array, a range, etc. Usually it’s sorted in ascending order. For most tasks, we can transform the requirement into the following generalized form:
Minimize k , s.t. condition(k) is True
The following code is the most generalized binary search template:
def binary_search(array) -> int:
def condition(value) -> bool:
pass
left, right = min(search_space), max(search_space) # could be [0, n], [1, n] etc. Depends on problem
while left < right:
mid = left + (right - left) // 2
if condition(mid):
right = mid
else:
left = mid + 1
return leftWhat’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:
- Correctly initialize the boundary variables
leftandrightto specify search space. Only one rule: set up the boundary to include all possible elements; - Decide return value. Is it
return leftorreturn left - 1? Remember this: after exiting the while loop,leftis the minimal k satisfying theconditionfunction; - Design the
conditionfunction. This is the most difficult and most beautiful part. Needs lots of practice.
Below I’ll show you guys how to apply this powerful template to many LeetCode problems.
>> Basic Application
278. First Bad Version [Easy]
You 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.
Example:
Given n = 5, and version = 4 is the first bad version.
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.First, 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:
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int low = 0;
int high = n;
int best=-1;
while(low<=high){
int mid = low+(high-low)/2;
if(isBadVersion(mid)){
best=mid;
high=mid-1;
} else{
low=mid+1;
}
}
return best;
}
}69. Sqrt(x) [Easy]
Implement 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.
Example:
Input: 4
Output: 2Input: 8
Output: 2Easy one. First we need to search for minimal k satisfying condition k^2 > x, then k - 1 is the answer to the question. We can easily come up with the solution. Notice that I set right = x + 1 instead of right = x to deal with special input cases like x = 0 and x = 1.
class Solution {
public int mySqrt(int x) {
if(x<2) return x;
int low=1;
int high=x/2;
int best=-1;
long num;
while(low<=high){
int mid=low+(high-low)/2;
num=(long)mid*mid; // long is very impt...
if(num <= x){
best=mid;
low=mid+1;
}else{
high=mid-1;
}
}
return best;
}
}class Solution {
public:
int mySqrt(int x) {
// if y*y>x, and y is the smallest value to achieve this condition, we will
// be able to know that y is the ans...
// keep trying with y values from 1 to x...
int low = 1;
long long high = x + 1LL; // Use long long to avoid overflow
while(low<high){
long long mid = low + (high-low) / 2;
if((mid * mid) > x){
high=mid;
}else{
low=mid+1;
}
}
return low-1;
}
};
How is this easy....Follow up
What if you can only return a value of a certain precision, defined by eps?
class Solution {
public int mySqrt(int x, int eps) {
int low = 0;
int high = x/2;
while(low<=high){
int mid = low + (high-low)/2;
int prod = mid * mid;
if(prod <= x){
low=mid;
} else {
high=mid;
}
if(Math.abs(prod-x) <= eps){
return mid;
}
}
return -1;
}
}35. Search Insert Position [Easy]
Given 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.
Example:
Input: [1,3,5,6], 5
Output: 2Input: [1,3,5,6], 2
Output: 1Very 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.
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] >= target:
right = mid
else:
left = mid + 1
return left
// Non Biinary Search approach
public int searchInsert(int[] nums, int target) {
int index = 0;
for(int i=0; i<nums.length; i++){
if(target == nums[i]){
return i;
} else if (target > nums[i]){
index = i + 1;
}
}
return index;
}>> Advanced Application
The 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 realise 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.
As 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.
1011. Capacity To Ship Packages Within D Days [Medium]
A conveyor belt has packages that must be shipped from one port to another within D days. 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.
Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within D days.
Example :
Input: weights = [1,2,3,4,5,6,7,8,9,10], D = 5
Output: 15
Explanation:
A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10Note 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.Binary 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.
Next, 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 thansum(weights), because then we can ship all packages in just one day.
Now we’ve got all we need to apply our binary search template:
def shipWithinDays(weights: List[int], D: int) -> int:
def feasible(capacity) -> bool:
days = 1
total = 0
for weight in weights:
total += weight
if total > capacity: # too heavy, wait for the next day
total = weight
days += 1
if days > D: # cannot ship within D days
return False
return True
left, right = max(weights), sum(weights)
while left < right:
mid = left + (right - left) // 2
if feasible(mid):
right = mid
else:
left = mid + 1
return left
/// C++ Solution
class Solution {
public:
int IMPOSSIBLE = -1;
int shipWithinDays(vector<int>& weights, int days) {
// if ship has capacity x and can fulfill the requirements,
// any other bigger capacity can fulfill as well
// we just need to find the smallest x
// low = heaviest weight
// high = sum of all weights
int low = *std::max_element(weights.begin(), weights.end());
int high = std::accumulate(weights.begin(), weights.end(), 0);
int best = IMPOSSIBLE;
while(low<=high){
int mid = low + (high-low) / 2;
if(isCapacityEnough(mid, weights, days)){
// try smaller
best = mid;
high = mid-1;
} else {
// try bigger
low = mid + 1;
}
}
return best;
}
bool isCapacityEnough(int capacity, vector<int> weights, int days){
int currDays = 1;
int currCap = 0;
for(int w: weights){
currCap += w;
if(currCap > capacity){
currDays++;
currCap = w;
}
if(currDays > days){
return false;
}
}
return true;
}
};410. Split Array Largest Sum [Hard]
Given 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.
Example:
Input:
nums = [7,2,5,10,8]
m = 2Output:
18Explanation:
There 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.
If 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.
class Solution {
public int splitArray(int[] nums, int k) {
int sum = 0;
int max=nums[0];
for(int i=0; i<nums.length; i++){
sum+=nums[i];
max=Math.max(max, nums[i]);
}
int low = max;
int high=sum;
int best=0;
while(low<=high){
int mid = low+(high-low)/2;
if(feasible(mid, nums, k)){
best=mid;
high=mid-1;
} else{
low=mid+1;
}
}
return best;
}
public Boolean feasible(int maxSum, int[] nums, int k){
int currSum=0;
int group=1;
for(int i=0; i<nums.length; i++){
if((currSum+nums[i]) > maxSum){
group++;
currSum=0;
}
currSum+=nums[i];
if(group>k) return false;
}
return true;
}
}But 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.
Let’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.
875. Koko Eating Bananas [Medium]
Koko 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.
Koko 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.
Example :
Input: piles = [3,6,7,11], H = 8
Output: 4Input: piles = [30,11,23,4,20], H = 5
Output: 30Input: piles = [30,11,23,4,20], H = 6
Output: 23Very 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.
class Solution {
public int minEatingSpeed(int[] piles, int h) {
int max = piles[0];
for (int i = 0; i < piles.length; i++) {
max = Math.max(max, piles[i]);
}
int best = 0;
int low = 1;
int high = max;
while (low <= high) {
int mid = low + (high - low) / 2;
if (feasible(mid, piles, h)) {
best = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return best;
}
public boolean feasible(int speed, int[] piles, int h) {
long hours = 0; // Use long to prevent integer overflow
for (int pile : piles) {
hours += (long) Math.ceil((double) pile / (double) speed);
}
return hours <= h;
}
}1482. Minimum Number of Days to Make m Bouquets [Medium]
Given 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.
Examples:
Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: Let's see what happened in the first three days. x means flower bloomed and _ means flower didn't bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _] // we can only make one bouquet.
After day 2: [x, _, _, _, x] // we can only make two bouquets.
After day 3: [x, _, x, _, x] // we can make 3 bouquets. The answer is 3.Input: bloomDay = [1,10,3,10,2], m = 3, k = 2
Output: -1
Explanation: 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.Now 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 for more than d days.
class Solution {
public int minDays(int[] bloomDay, int m, int k) {
int max=1;
for(int i=0; i<bloomDay.length; i++){
max=Math.max(max, bloomDay[i]);
}
int low=1;
int high=max;
int best=-1;
while(low<=high){
int mid = low + (high-low)/2;
if(feasible(mid, bloomDay, k, m)){
best=mid;
high=mid-1;
} else {
low=mid+1;
}
}
return best;
}
public Boolean feasible(int days, int[] bloomDay, int flowers, int bouquets){
int currFlowers = 0;
int currBouquets = 0;
for(int bloom: bloomDay){
if(bloom>days){
// curr flower not bloomed yet. cannot be combined with neighbouring flowers to form bouquet
currFlowers=0;
} else {
currFlowers = (currFlowers + 1) % flowers;
currBouquets += (currFlowers == 0) ? 1 : 0; // make a new bouquet if current bouquet is already full
}
}
return currBouquets >= bouquets;
}
}668. Kth Smallest Number in Multiplication Table [Hard]
Nearly every one have used the 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.
Example :
Input: m = 3, n = 3, k = 5
Output: 3
Explanation:
The Multiplication Table:
1 2 3
2 4 6
3 6 9The 5-th smallest number is 3 (1, 2, 2, 3, 3).For 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.
Let’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.
Next 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.
def findKthNumber(m: int, n: int, k: int) -> int:
def enough(num) -> bool:
count = 0
for val in range(1, m + 1): # count row by row
add = min(num // val, n)
if add == 0: # early exit
break
count += add
return count >= k
left, right = 1, n * m
while left < right:
mid = left + (right - left) // 2
if enough(mid):
right = mid
else:
left = mid + 1
return left
// C++
class Solution {
public:
int findKthNumber(int m, int n, int k) {
// binary search
// given an input num, determine whether there're at least k values less than or equal to num
int low = 1;
int high = m*n;
while(low<high){
int mid = low + (high-low) / 2;
if(validate(mid, k, m, n)){
high=mid;
} else {
low = mid+1;
}
}
return low;
}
bool validate(int num, int k, int m, int n){
int count = 0;
for(int i=1; i<m+1; i++){
int add = std::min(num / i, n);
// num/i determines the maximum number that can be present in each row of the grid while still being smaller than or equal to num.
// n: number of columns. In case all numbers in the row are smaller than num, then we take column to be the max add.
/*
* calculates the maximum number that can be present in each row of the grid without exceeding num, while considering the smaller value between the division result and the total number of columns.
*/
if (add == 0) break;
count += add; // number of number that is smaller than num
}
return count >= k;
}
};In 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 - 1) would also return True, same as 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.
Explaining std::min(num / i, n);
For example, let’s consider a scenario where num is 5, m (number of rows) is 3, and n (number of columns) is 4. The grid would look like this
1 2 3
2 4 6
3 6 9Now, let’s go through the loop iterations:
- In the first iteration,
iis 1. The lineint add = std::min(num / i, n)becomesint add = std::min(5 / 1, 3), which isint add = std::min(5, 3). Since 5 is greater than 3,addtakes the value of 3. -> There can only be at maximum, 3 numbers in this row. - In the second iteration,
iis 2. The lineint add = std::min(num / i, n)becomesint add = std::min(5 / 2, 3), which isint add = std::min(2, 3). Here, we take 2. (There are 2 numbers, 2,4 that are smaller than 5). - In the third iteration,
iis 3. The lineint add = std::min(num / i, n)becomesint add = std::min(5 / 3, 3), which isint add = std::min(1, 3). Here,addtakes the value of 1.
719. Find K-th Smallest Pair Distance [Hard]
Given 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.
Example :
Input:
nums = [1,3,1]
k = 1
Output: 0
Explanation:
Following are all the pairs. The 1st smallest distance pair is (1,1), and its distance is 0.
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2Very 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:
def enough(distance) -> bool: # two pointers
count, i, j = 0, 0, 0
while i < n or j < n:
while j < n and nums[j] - nums[i] <= distance: # move fast pointer
j += 1
count += j - i - 1 # count pairs
i += 1 # move slow pointer
return count >= kObviously, our search space should be [0, max(nums) - min(nums)]. Now we are ready to copy-paste our template:
def smallestDistancePair(nums: List[int], k: int) -> int:
nums.sort()
n = len(nums)
left, right = 0, nums[-1] - nums[0]
while left < right:
mid = left + (right - left) // 2
if enough(mid):
right = mid
else:
left = mid + 1
return leftclass Solution {
public:
int smallestDistancePair(vector<int>& nums, int k) {
std::sort(nums.begin(), nums.end());
int left = 0;
int right = *std::max_element(nums.begin(), nums.end()) - *std::min_element(nums.begin(), nums.end());
while(left<right){
int mid = left + (right-left) / 2;
if(validate(mid, k, nums)){ // have k num of pairs with diff <= mid
right = mid; // try with a smaller mid
} else {
left = mid + 1;
}
}
return left;
}
bool validate(int distance, int k, vector<int>& nums){
int count = 0;
int i = 0;
int j = 0;
int n = nums.size();
while(i<n || j<n){
while(j<n && nums[j]-nums[i]<=distance){
j++; // move right pointer
}
count += j-i-1; // count pairs..remove 1 value from j since this j caused diff to be more than distance
i+=1; // move left pointer
}
return count >= k;
}
};1201. Ugly Number III [Medium]
Write a program to find the n-th ugly number. Ugly numbers are positive integers which are divisible by a or b or c.
Example :
Input: n = 3, a = 2, b = 3, c = 5
Output: 4
Explanation: The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10... The 3rd is 4.Input: n = 4, a = 2, b = 3, c = 4
Output: 6
Explanation: The ugly numbers are 2, 3, 4, 6, 8, 9, 10, 12... The 4th is 6.Nothing 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.
def nthUglyNumber(n: int, a: int, b: int, c: int) -> int:
def enough(num) -> bool:
total = num//a + num//b + num//c - num//ab - num//ac - num//bc + num//abc
return total >= n
ab = a * b // math.gcd(a, b)
ac = a * c // math.gcd(a, c)
bc = b * c // math.gcd(b, c)
abc = a * bc // math.gcd(a, bc)
left, right = 1, 10 ** 10
while left < right:
mid = left + (right - left) // 2
if enough(mid):
right = mid
else:
left = mid + 1
return left
class Solution {
public:
int nthUglyNumber(int n, int a, int b, int c) {
long long ab = static_cast<long long>(a) * b / std::gcd(a, b);
long long ac = static_cast<long long>(a) * c / std::gcd(a, c);
long long bc = static_cast<long long>(b) * c / std::gcd(b, c);
long long abc = static_cast<long long>(a) * bc / std::gcd(a, bc);
long long left = std::min(std::min(a, b), c), right = pow(10, 10);
while (left < right) {
long long mid = left + (right - left) / 2;
if (enough(mid, n, a, b, c, ab, ac, bc, abc)) {
right = mid;
} else {
left = mid + 1;
}
}
return static_cast<int>(left);
}
/*
* determines whether a given number num has enough ugly numbers that are divisible by a, b, or c.
* num / a gives the count of numbers divisible by a up to num.. vice versa
num / ab gives the count of numbers divisible by both a and b up to num. Since ab is the least common multiple of a and b, this gives the count of numbers divisible by ab up to num. However, some of these numbers may be counted in num/a and num/b, so we remove them...
inclusion-exclusion principle
|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|
*/
bool enough(long long num, long long n, long long a, long long b, long long c, long long ab, long long ac, long long bc, long long abc) {
long long total = num / a + num / b + num / c - num / ab - num / ac - num / bc + num / abc;
return total >= n;
}
};1283. Find the Smallest Divisor Given a Threshold [Medium]
Given 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.
Each 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.
Example :
Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1.
If 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).After 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.
def smallestDivisor(nums: List[int], threshold: int) -> int:
def condition(divisor) -> bool:
return sum((num - 1) // divisor + 1 for num in nums) <= threshold
left, right = 1, max(nums)
while left < right:
mid = left + (right - left) // 2
if condition(mid):
right = mid
else:
left = mid + 1
return leftclass Solution {
public:
int smallestDivisor(vector<int>& nums, int threshold) {
int low = 1;
int high = *std::max_element(nums.begin(), nums.end());
// try out all the divisor
while(low<high){
int mid = low + (high-low)/2;
if(feasible(mid, threshold, nums)){
high=mid;
} else{
low=mid+1;
}
}
return low;
}
bool feasible(int divisor, int threshold, vector<int>& nums){
int sum = 0;
for(int n: nums){
sum += n/divisor + (n%divisor>0);
}
return sum<=threshold;
}
};Take note that the condition might not always be int mid = low + (right-low) / 2; For example below…
1231. Divide Chocolate
You have one chocolate bar that consists of some chunks. Each chunk has its own sweetness given by the array sweetness.
You want to share the chocolate with your k friends so you start cutting the chocolate bar into k + 1 pieces using k cuts, each piece consists of some consecutive chunks.
Being generous, you will eat the piece with the minimum total sweetness and give the other pieces to your friends.
Find the maximum total sweetness of the piece you can get by cutting the chocolate bar optimally.
Example 1:
Input: sweetness = [1,2,3,4,5,6,7,8,9], k = 5
Output: 6
Explanation: You can divide the chocolate to [1,2,3], [4,5], [6], [7], [8], [9]Example 2:
Input: sweetness = [5,6,7,8,9,1,2,3,4], k = 8
Output: 1
Explanation: There is only one way to cut the bar into 9 pieces.Example 3:
Input: sweetness = [1,2,2,1,2,2,1,2,2], k = 2
Output: 5
Explanation: You can divide the chocolate to [1,2,2], [1,2,2], [1,2,2]class Solution {
public:
int maximizeSweetness(vector<int>& sweetness, int k) {
// try out all possible sums and see which valid split gives minimum.
// if i can find a sum that is true, then sum+1 is true..
// need the minimum
// try out all possible sweetness that i can get
// low: min of sweetness
// high: sum of sweetness
// feasible: check if i can divide arr into k parts if i use this sweetness
int low = *std::min_element(sweetness.begin(), sweetness.end());
int high = std::accumulate(sweetness.begin(), sweetness.end(), 0) / (k + 1);
std::cout << high << endl;
std::cout <<low<< endl;
while(low<high){
int mid = low + (high-low + 1) / 2; // Need to +1 to avoid infinite loop
// using int mid = low + (high - low) / 2; can cause an infinite loop when high and low are adjacent integers due to rounding down to the lower integer value. 1 + (2-1) / 2 -> mid = 1
if(feasible(mid, k + 1, sweetness)){
low = mid; // check if the current mid value can be increased (cus we want the maximum)..try with bigger vals
} else {
high = mid - 1;
}
}
return high;
}
bool feasible(int threshold, int segmentsRequired, vector<int>& sweetness){
int seg = 0;
int total = 0;
for(int sweet: sweetness){
total+=sweet;
if(total>=threshold){
seg+=1;
total = 0;
}
}
if(seg>=segmentsRequired){ // all seg can have at least threshold sum and we can have at least segmentsRequired segments
return true;
}
return false;
}
};The template is slightly modified for this question. After we found a mid that satisfies the condition, we will try to see if we can increment and try with bigger value than mid. (Whereas, for other previous qns, we try to decrement it). I am not sure if this has to do with the need for +1.
For the test case:
Input: sweetness = [1,2,3,4,5,6,7,8,9], k = 5
Output: 6
Explanation: You can divide the chocolate to [1,2,3], [4,5], [6], [7], [8], [9]
If I log the low, mid, high values, i get:
1 4 7
4 6 7
6 7 7
If I remove +1 from the mid statement, I get an infinite loop:
1 4 7
4 5 7
5 6 7
6 6 7
6 6 7
...Update:
A better approach is to use the one below.. will summarise it at the end of this article…(See section on tips from a smart friend)
class Solution {
public:
const int IMPOSSIBLE = -1;
int maximizeSweetness(const std::vector<int> &sweetness, int num_friends)
{
int num_people = num_friends + 1;
int low = *std::min_element(sweetness.begin(), sweetness.end());
int high = std::accumulate(sweetness.begin(), sweetness.end(), 0) / num_people;
int best_answer_so_far = IMPOSSIBLE;
// Goal: Highest sweetness/threshold where is_feasible() is True.
// Range appearance: [TTTTTTTTTFFFFFFFFF]
// ^---->
while (low <= high)
{
int mid = low + (high - low) / 2;
if (is_feasible(mid, num_people, sweetness))
{
best_answer_so_far = mid;
// Search right
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return best_answer_so_far;
}
bool is_feasible(int threshold, int num_segments_required, const std::vector<int> &sweetness)
{
int current_sweetness = 0;
int num_segments = 0;
for (int chunk_sweetness : sweetness)
{
current_sweetness += chunk_sweetness;
if (current_sweetness >= threshold)
{
current_sweetness = 0;
++num_segments;
}
}
return num_segments >= num_segments_required;
}
};774. Minimize Max Distance to Gas Station
You are given an integer array stations that represents the positions of the gas stations on the x-axis. You are also given an integer k.
You should add k new gas stations. You can add the stations anywhere on the x-axis, and not necessarily on an integer position.
Let penalty() be the maximum distance between adjacent gas stations after adding the k new stations.
Return the smallest possible value of penalty(). Answers within 10-6 of the actual answer will be accepted.
Example 1:
Input: stations = [1,2,3,4,5,6,7,8,9,10], k = 9
Output: 0.50000Example 2:
Input: stations = [23,24,36,39,46,56,57,65,84,98], k = 1
Output: 14.00000Editorial solution
class Solution {
public:
public:
double minmaxGasDist(std::vector<int>& stations, int K) {
double lo = 0, hi = 1e8;
while (hi - lo > 1e-6) {
double mi = (lo + hi) / 2.0;
if (possible(mi, stations, K))
hi = mi;
else
lo = mi;
}
return lo;
}
bool possible(double D, std::vector<int>& stations, int K) {
int used = 0;
for (int i = 0; i < stations.size() - 1; ++i)
used += static_cast<int>((stations[i + 1] - stations[i]) / D);
return used <= K;
}
};
275. H-Index II
Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper and citations is sorted in ascending order, return the researcher's h-index.
According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.
You must write an algorithm that runs in logarithmic time.
Example 1:
Input: citations = [0,1,3,5,6]
Output: 3
Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.Example 2:
Input: citations = [1,2,100]
Output: 2class Solution {
public:
int hIndex(vector<int>& citations) {
int low = 0;
int high = citations.size()-1;
int best = -1;
int size = citations.size();
// We need to find the rightmost 'index' such that: (citations[index] <= n - index)
while(low<=high){
int mid = low + (high-low) / 2;
if(checkValid(citations, mid)){
best = max(citations[mid], best);
low = mid + 1; // can go higher?
} else {
best = max(best, size-mid); // the best number could be num of elements to the right of mid index
// eg, [0,0,4,4] -> best: 2
high = mid - 1; // need to go lower..
}
}
return best;
}
bool checkValid(vector<int>& citations, int index){
int val = citations[index];
int rightElementCount = citations.size()-index;
return rightElementCount >= val;
}
};Tips from a Smart Friend
We need to define a few things first.
- What does the search space contain?
- Do we want to have low and high both inclusive or both exclusive or one incusive and another exclusive? (The one given in the leetcode discussiont template belongs to the last category)
- Will the search range contain the best value you have found so far, or range that you have not searched yet? (Ans: The latter)
In the template code given in this entire article (from the top), we have [low, high) where Low inclusive and High exclusive. This makes things confusing and should be avoided.
It’s best to have [low, high]. Both inclusive.
And then, each new search range is performed on a range that has not been seen before.
In the condition, always use int mid = low + (high — low) / 2; This makes sure that our code won’t be buggy even if we have to deal with negative values and mid will always be the middle of low and high.
The template we should follow is:
- include both low and high. Low inclusive, high inclusive. Means that the condition becomes while(low≤high). The reason why we need an equality is because if we reach the case where low = high, we still want to continue the loop since it indicates our search space still has 1 element and we want to look at it.
- We can define that everything inside our search range (low and high) are items that have not been looked at yet and hence, we want to look at them.
- Define our Goal. It can be something like finding largest index where False…We will need to read the question and draw out the range to figure out our goal. Eg
[TTTTTTTTTFFFFFFFFF]
^---->
If isFeasible() function evaluates to True, then we want to check
if that is the highest, so our new search range will be on the right.4. Keep track of another variable bestAnswerSoFar. In this case, we don’t need to care how we are doing the search, such as where low and high is. In the template given at the top, see that we return left. This can be confusing.
5. Make sure our search space always reduces, so that we don’t hit an infinite loop. For example, we always do mid + 1 or mid — 1. This ensures we don’t look at mid for more than once.
Therefore, the new template we can adopt is:
while (low <= high)
{
int mid = low + (high - low) / 2;
if (is_feasible(mid, num_people, sweetness))
{
best_answer_so_far = mid;
// Search right
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return best_answer_so_far;The reason why i didn’t use this template for the questions above is because i am currently lazy to update the code and i only knew of these tips after completing most of the questions above based on the suggestions given by the leetcode article.
