A week of Leetcode (day 4/7)
Welcome to the fourth episode of our technical interview preparation series. Our goal is to pave the way for you to land your dream job with ease by providing you with real problem-solving skills covering lots of topics.
Don’t forget to check the rest of the series:
- Day (1/15): Basic arithmetic
- Day (2/15): Two pointers technique
- Day (3/15): Greedy thinking
- Day (4/15): Binary Search + BSGS + PIE
Let’s not waste time and jump right in!
Day 4: Ugly Number III
I will assume you haven’t read the task description, so here is a summary:
Given four numbers n, a, b, and c.
print the nth number that is divisible by a, b or c.
Disclaimer: Don’t fall for the short statement and easy prompt. This problem is an imposter.
First Attempt: Brute-force
Loop over numbers starting from one, enumerating the numbers that are divisible by a, b or c, then stop when your counter hits n.
This is absolutely correct, but is it efficient?
This is an O(N) solution but as n can go up to 10⁹ this takes a lot of time to run. At the end of this article we will find a solution that runs in under 50 milliseconds!
Let’s set some metrics to give us feedback about the goodness of our solutions based on:
- Correctness (does that solution give me a correct answer?)
- Efficiency (How much time should I wait to get an answer?)
These criteria are enough to decide whether we are doing the right thing or we give up and consider a different approach.
Let’s evaluate the goodness of our Bruteforce guy:
Correctness: 10/10
Efficiency: 2/10, It runs fast for small inputs but incredibly slow otherwise.
Overall: 6/10, not very great :(
We need to do better, don’t we?
As always, we try to break the problem into smaller sub-problems.
The smaller sub-problems:
Let’s try to solve the same problem with the condition that a = b = c.
It turns out that we have a closed-form formula to calculate the answer in that case (come up with it as an exercise), but let’s pretend that we don’t know it.
We also define a helper function (a function that does some side-work to help us with our task). Bear with me please, you will know why we are doing that very soon.
we define the helper function “Count_Ugly” that takes X as input and returns the count of ugly numbers less than or equal to X.
Now we would like to know the smallest number m, s.t Count_Ugly(m) = n, our final answer is m, this is often referred to as a Lower Bound query.
Fact: Count_Ugly doesn’t decrease, that is Count_Ugly(x+1) ≥ Count_Ugly(x), can you see why?
Whenever you run into a situation when you have an increasing function, going for binary search is an option to consider, but what is binary search?!
This is how the binary search looks like :)
A brief description of binary search:
The binary search is smart, it doesn’t do the unnecessary computations using the fact that the function is non-decreasing to reduce the number of its iterations astronomically, let’s have a closer look to understand what is going on.
Binary Search in action:
1- Define the range [L, R] that you want to inspect, simply you are telling the algorithm “hey binary search, I want you to look up the answer for me, it is somewhere between L and R, but I don’t know the exact location”.
2- Find the middle number in the Range [L, R], a standard way is to use the formula M = (L + R) / 2 (rounding down).
3- Now comes the crucial part: the algorithm examines M closely and based on that it decides what to do next.
-The first scenario is Count_Ugly(M) < n, which implies that Count_Ugly of any guy in [L, M] is less than n, implying that our answer is somewhere in [M + 1, R], so just adjust your borders [L, R] to the new range [M+1, R] and run another iteration.
-The second scenario is Count_Ugly(M) ≥ n, which implies that M is a candidate answer, but we can’t tell for sure if it is the smallest possible answer, what we know is we should ignore any number in the range [M + 1, R] because M is a better candidate than all of them (remember we are looking for the smallest answer), now adjust your range [L, R] to be [L, M-1], and do another iteration to check if there an answer that is better than M.
4- Eventually you will end up with L = R = M, this is the final iteration of the algorithm, and checking M is enough to know the final answer, if Count_Ugly(M) < n, then return M + 1, otherwise return M.
Confused? Let’s try an example.
N = 5, a = b = c = 3
Define a big enough range so that you are confident to find the answer inside. For illustration purposes, we will set [L, R] to [1, 20] but in practice, the range will be much larger.
Iteration 1:
L = 1, R = 20, M = 10
Count_Ugly(10) = 3, that is less than n so we need to turn right as the range [L, M] is just useless.
Iteration 2:
L = 11, R = 20, M = 15
Count_Ugly(15) = 5, well that is nice, we are able to find an answer in just two iterations, who dreamt of that, but we should be skeptical not to overlook the range [L, M-1] as there may be a smaller answer inside, so let’s adjust our range and see what happens.
Iteration 3:
L = 11, R = 14, M = 12
Count_Ugly(12) = 4 < n, turn right.
Iteration 4:
L = 13, R = 14, M = 13
Count_Ugly(13) = 4 < n, turn right.
Iteration 5:
L = R = M = 14
Count_Ugly(14) = 4 < n, that is enough to say for sure that 14 + 1 = 15 is the smallest answer that exist.
We have our answer in 5 iterations, instead of 15 if we run the linear search (aka brute-force).
How fast is binary search? I will omit any mathematical terms, for now, to keep this tutorial beginner-friendly as much as possible.
Instead, I will try to convince you that this is really fast even if the range is huge.
Time analysis of binary search:
We start with S numbers in the range (S = R-L+1).
After each iteration, we ignore almost half of the range. Let’s do a simulation to convince you more.
S =1024 > 512 > 256 > 128 > 64 > 32 > 16> 8 > 4 > 2 > 1
Look how we checked a range with more than a thousand elements using only 10 iterations. In fact, binary search is one of the fastest search algorithms in many scenarios. It has a time complexity of ( log N).
Let’s evaluate the goodness of our binary search guy:
Correctness: 10/10, cool!
Efficiency: 10/10, the algorithm runs fairly quickly for small and big inputs.
Overall: 10/10, that is the guy you need:)
There are many approaches to answer the lower bound queries that we can try:
Meta Binary Search:
This is slightly different from what we have just done, it is based on the binary representation of the answer.
The meta binary search finds the largest number L with Count_Ugly(L) < n, and then adds one to L and says that is the answer.
It iterates over the powers of two from the largest to the smallest, and try to add it to the answer, and checks if Count_Ugly(current_answer) is < n, in that case, it does nothing, otherwise it undoes that step, and proceeds to the next power of two.
Pseudocode:
LowerBound(n)
big_power = a big enough power of two
answer = 0 for i from big_power to 0
add 2^i to answer
if Count_Ugly(answer) >= n
substract 2^i from answer
return answer + 1
This is just another perspective of binary search which has a fixed number of iterations.
We often start from 2⁶³ and that is more than enough in almost all the cases, but you can set a smaller power of two as a starting point depending on how big the final answer could be.
Baby Step/ Giant Step ( square root decomposition):
This is another approach you can try, let’s begin with a scenario:
You want to travel from your university dorm in city X, to your home in city Y, you take the bus and it takes you to the desired destination Y, you get off the bus and walk down the street until you reach your house, congratulations you just applied the baby step/giant step (BSGS) algorithm.
The BSGS is very simple. It says “if you want to go from point A, to point B, start by making big strides, until you get close enough to B, then you slow down and start making small steps until you hit B.
In the above scenario, you took the bus (which accounts for the giant steps), that is at each step takes you to a different city, and when you got off, you started waking (which represents the small steps).
The running time of this algorithm depends on the size of your big step S.
If the distance is N, then choosing S yields the following results:
- we make N / S big steps (rounded down), if you make more than that you will overshoot the target.
- We make at most S small steps, if you make more than S small steps, then why didn’t you make a big step instead?!
That is (S + N / S) in total, this sum is the smallest possible when S is around the square root of N, it becomes ( sqrt(N) + N / sqrt(N) ) = 2 * sqrt(N).
Which is just O( sqrt(N) ), and that is fast enough in a lot of cases.
Pseudocode:
LowerBound(n)
big = squart_root(n)
small = 1
answer = 0 while Count_Ugly( answer + big) < n
answer += big while (count_Ugly + small ) < n
answer += small return answer + 1
Remember, this is not the actual problem, but solving it is a great milestone in solving the big thing.
The general case:
But we can’t celebrate right now, as we have only solved a special case of the general problem. We made a constraint that a = b = c, but that is not the case in general.
It turns out that we only need to find Count_Ugly quickly. The best we can do is to find an O(1) formula, but it isn’t particularly obvious.
But how did we calculate Count_Ugly when a = b= c?
That is a simple question. It is just a simple division.
Fact: The count of numbers divisible by X in the range [1, N] is N / X (rounded down).
To generalize the idea, let’s recall the Principle of Inclusion-Exclusion (PIE)
In simple words, this principle says if you want to enumerate the stuff that satisfies one of two conditions, you do the following:
Let S1 be the count of stuff that satisfies the first condition and similarly define S2 to the number of stuff that satisfies the second condition.
Define S12 to be the count of the things that satisfy both of the conditions.
Your answer is S1+S2 -S12
Notice that we subtract S12 because they are added twice, as they are double-counted in S1 and S2, so we should subtract the quantity.
Example:
Let say we are interested in the count of numbers that are divisible by either 3 or 5 in the range [1, 20]
The PIE doesn’t talk too much, but it lets you have a look and see for yourself the inner calculations (how kind!).
S1 = how many numbers in [1, 20] are divisible by 3, that’s 20 / 3 rounded down = 6
S2= how many numbers in [1, 20] are divisible by 5, that is 20 / 5 rounded down = 4
S12 = how many numbers in [1, 20] are divisible by 3 and 5, that is trickier to calculate, but still manageable, just recall the fact that if Z divides A, and B then Z divides the LCM (least common multiple of A and B), LCM(3,5) = 15, so S12 = 20 / 15 rounded down = 1
S1 + S2- S12 = 6 + 4–1 = 9, so PIE yells “9 is the answer”.
If this is your first time dealing with PIE, you may be skeptical (which is a good thing), so let’s double-check what we have got.
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
The numbers in bold are the answer, and we have 9 of them, so you should have at least some faith in the power of PIE.
Why limit ourselves to two conditions, actually PIE doesn’t care about the number of them.
In our case, we have three conditions.
- Sxyz is the count of the things that satisfy the x-th, y-th and z-th conditions at the same time.
- Sxy is the count of the things that satisfy both the x-th and y-th conditions.
- Sz is the count of the things that satisfy condition z.
Now PIE’s job is more sophisticated:
It calculates S1, S2, S3, S12, S13, S23, S123
And the final answer is S1 + S2 + S3- S12 -S23-S13+ S123. Convince yourself that we are not double-counting any stuff.
That’s all we need, let’s write some code:
My C++ Implementation
My Python Implementation
How we approached today’s task, and how to approach other challenges?
- Break the problem in your hand into smaller sub-problems: this technique is very useful, as smaller problems tend to have simpler and sometimes well-known solutions.
- Think about how to solve the smaller sub-problems efficiently and combine them into one final happy solution.
- Change the setting of the problem and make assumptions that help you better interpret the problem in front of you: notice that we assumed a = b = c, and later we found a general solution.
- Reread this article many times until you fully appreciate it, especially if it is your first time to see binary search or Principle of Inclusion-Exclusion in action.
Your Turn:
Congratulations! If you made it here in one sitting, I knew you could do it.
Now that you hopefully acquired some new skills, Don’t stop here, put them into practice.
Go play with the code, write it by yourself from scratch, and challenge yourself to come up with examples of problems that could be solved using binary search.
Take it to the next step by inventing your own way of solving a lower bound query, good luck ;)
Additional Problems for practice:
