Output should be 14 instead of 12
Thank you for pointing out. We will fix it.
The explanation isn’t very clear on what the solution is doing: especially what is ugly_number_count doing?
ugly_number_count(k) calculates the number of ugly numbers less than or equal to k. e.g.
a = 2, b = 3, c = 5, k = 14
ugly_number_count would return 10, the numbers are 2, 3, 4, 5, 6, 8, 9, 10, 12, 14
14//2 = 7, which means there are 7 numbers <= 14 and divisible by 2, namely 2, 4, 6, 8, 10, 12, 14
14//3 = 4, which means there are 3 numbers <= 14 and divisible by 3, namely 3, 6, 9, 12
14//5 = 2, which means there are 2 numbers <= 14 and divisible by 5, namely 5, 10
Note there are duplicates from the numbers above, e.g. 6 is divisible by 2 and 3 and 10 is divisible by both 2 and 5.
To filter out the duplicates, we use the Venn Diagram from above.
Total number divisible by either 2, 3 or 5 = number divisible by 2 + number divisible by 3 + number divisible by 5 - number divisible by 2 and 3 - number divisible by 2 and 5 - number divisible by 3 and 5 - number divisible by 2, 3 and 5
https://math.stackexchange.com/questions/933482/need-help-solving-a-venn-diagram
ugly_number_count(k) calculates the number of ugly numbers less than or equal to k. e.g. a = 2, b = 3, c = 5, k = 14
ugly_number_count would return 10, the numbers are 2, 3, 4, 5, 6, 8, 9, 10, 12, 14
14//2 = 7, which means there are 7 numbers <= 14 and divisible by 2, namely 2, 4, 6, 8, 10, 12,
14 14//3 = 4, which means there are 3 numbers <= 14 and divisible by 3,
namely 3, 6, 9, 12 14//5 = 2, which means there are 2 numbers <= 14 and divisible by 5, namely 5, 10
Note there are duplicates from the numbers above, e.g. 6 is divisible by 2 and 3 and 10 is divisible by both 2 and 5.
To filter out the duplicates, we use the Venn Diagram from above.
Total number divisible by either 2, 3 or 5 = number divisible by 2 + number divisible by 3 + number divisible by 5 - number divisible by 2 and 3 - number divisible by 2 and 5 - number divisible by 3 and 5 - number divisible by 2, 3 and 5
https://math.stackexchange.com/questions/933482/need-help-solving-a-venn-diagram
Can you please explain below boundary conditions?
min_ptr = n
max_ptr = n * min(a, b, c)
So we are just supposed to know or figure out this formula to find ugly numbers?
My biggest hangup on this problem is the math. Given a number X, how can I calculate which ugly number it is? I understand the intuition behind X // a, X // b, X // c - and I understand that this over counts the ugly number idx. This is where I got stuck.
What is the intuition behind these? How did GCD make it’s way into this? Could I expect math help on an interview?
ab = a * b // gcd(a, b)
bc = b * c // gcd(b, c)
ac = a * c // gcd(a, c)
I don’t understand how ‘ab = a * b // gcd(a, b)’ was derived. Is this some pre existing maths formular?
Hi, ab is the least common factor (LCM) and it’s equal to a*b / GCD. e.g.
a = 15
b = 6
gcd(a,b) = 3
a*b = 15*6=90
lcm(a,b)=90/3=30
As per the definition of ugly number, it is a positive number whose prime factors are limited to a,b and c.
Consider 14 is not an ugly number because 14/2 = 7 and 7 is further not divisible by either 2,3 or 5. Thus 14 is not an ugly number.
Consider 15, 15 is divisible by 3 i.e. 15/3 =5 and 5 is further divisible by 5 i.e 5/5 = 1 and as the final answer is 1, 15 becomes ugly number.
Consider 12, 12 is divisible by 2, i.e 12/2 = 6 and 6 is further divisible by 2 i.e. 6/2= 3 and 3 is further divisible by 3 i.e 3/3 =1 , as the final answer is 1, 12 is an ugly number.
I think the logic needs to be corrected or let me know if this is not the current definition of ugly number.
I think your Java solution for Test #5 is overflowing.
I implemented this using long’s (not int’s) and got 42,830,665,558 for an answer.
Since the number can be too large, return the actual answer modulo 10^9 + 7
I also don’t understand why the upper bound is n * min(a, b, c). Any explanation?
Jesus Freaking Christ!!!
I can’t imagine writing this code during an interview… I’m doomed.
hahaha
Pretty disappointed with the quality of the explanations as I’ve progressed through AlgoMonster so far. Started off strong, but as I’ve entered the “advanced” categories of particular topics, the problem descriptions and explanations have seemed more hastily and poorly written. This is not what I expected from the upfront cost, and I’m hoping it improves as I continue.
How did you determine that the answer lies between n and [n * min(a, b, c)]?