Your multiplication solution is not exactly correct. For example, 2*7 is not an ugly number. Your DP solution is correct though.The basic concept is any ugly number multiplied with 2,3 or 5 will give an ugly number.As we only keep ugly numbers in the dp array, we will get the answer
hE means to say: do the multiplication in the following way : if (ugly == nums[i2] * 2) ++i2; if (ugly == nums[i3] * 3) ++i3; if (ugly == nums[i5] * 5) ++i5;
The DP algorithm does not solution this problem. For example, 14 is not an ugly number in your example, but you counted as a multiple of 2. I made the same mistake before.
i think this approach deviates at a point wherein the 11th ugly number comes 2*7=14 which is incorrect, the dp solution is a thing after that but i think something is wrong in the main approach!!!
out of thin air you thought you should use 2,3,5 tables ? you should've explained what made you use that method instead of just explaining the code in English.
Thank you for the explanation Bhaiya :) But your intuitive solution is misleading. In your intuitive solution, you are basically taking a minimum number from tables of 2,3 and 5 at each iteration, by this approach, we will even have 14,21.... and so on as an ugly number which is incorrect. Though, final dp approach is correct.
Why are 14 and 21 not ugly numbers though? 14 = 7 * 2. 2 is in the provided set. Same with 21 = 7 * 3. Edit: I believe it's because it needs to have both factors be in the set. Both 14 and 21 each only have one in the set
The approach using something like bfs only to store it in a TreeSet so that they remain in an order and continuing until the interation reaches to can be something that works. But i dont think it involves dp.
Guys, this approach is wrong. Using a multiplication table means that at some point you will insert 14(2*7) or 21(3*7) and so on, which are not ugly numbers.
because every number can only be divided by 2, 3, 5, one way to look at the sequence is to split the sequence to three groups as below: (1) 1×2, 2×2, 3×2, 4×2, 5×2, … (2) 1×3, 2×3, 3×3, 4×3, 5×3, … (3) 1×5, 2×5, 3×5, 4×5, 5×5, … We can find that every subsequence is the ugly-sequence itself (1, 2, 3, 4, 5, …) multiply 2, 3, 5. Then we use similar merge method as merge sort, to get every ugly number from the three subsequence. Every step we choose the smallest one, and move one step after.
how to write a recursive formula for this problem? because generally for all the dp problems I have been seeing some recursive formula, why not in this problem?
Let me tell you this guy just copy the solution from one source and then make a video of them. I have the algorithm to generate ugly numbers which I wrote. I will paste it here.
@@swarnikagupta16 see the apprach is that for ugly number you have a choice to multiply it with 2,3 and 5. Each multiplication will give you an ugly number. so recursion node will be splitting into 3 more nodes. Create an ugly number HashSet. Suppose you want to generate 100 ugly numbers. We will check if that ugly number is in the HashSet then we will not add it and will end the recursion process there. see this is a pseudo code solution so focus on the approach, not on syntax. int N = 100; // total number of ugly numbers to generate. Hashset hashset = new Hashset(); totalNumbersGenerated; public void uglyGenerator(int num,int totalNumbersGenrated, int N, Hashset hashset){ if(hashSet.contains(num) || (totalNumbersGenerated==N)) { return ; // this will help to terminate the multiple subproblems} else if (hashSet.contains(num)!=true) { totalNumbersGenerated += 1; hashset.add(num); uglyGenerator(num*2); uglyGenerator(num*3); uglyGenerator(num*5); } } But here is a problem in the solution. It will not generate the ugly numbers in sorted order.
if the numbers are already present in the array then what should we do? ex:-[1,2,3,4,5,6,8,9,10] i1,i2,i3=10,9,10 then what should we do ? from now it is getting wrong for me.
Your multiplication solution is not exactly correct. For example, 2*7 is not an ugly number. Your DP solution is correct though.The basic concept is any ugly number multiplied with 2,3 or 5 will give an ugly number.As we only keep ugly numbers in the dp array, we will get the answer
hE means to say:
do the multiplication in the following way :
if (ugly == nums[i2] * 2) ++i2;
if (ugly == nums[i3] * 3) ++i3;
if (ugly == nums[i5] * 5) ++i5;
@@kedarnadkarni8781 see around 10:12
your approach with the multiplication table is wrong, try to upload videos with right concept, otherwise it'll be confusing for others
yes bro.he made me confuse for a while
The DP algorithm does not solution this problem. For example, 14 is not an ugly number in your example, but you counted as a multiple of 2. I made the same mistake before.
Ditto... the answer is wrong!!!! Don't follow this algo...
yes its wrong...wasted almost an hour
i think this approach deviates at a point wherein the 11th ugly number comes 2*7=14 which is incorrect, the dp solution is a thing after that but i think something is wrong in the main approach!!!
Actually 1 is also a power of those,2 power 0 is 1,3 power 0 is 1,5 power 0 is 1 at(1:03)
I don't understand the way we uptade the next number ugly number (nm2= ugly[i2] * 2). I mean, why does it work?
DP approach is mind-blowing.
:)
Your multiplication solution is not exactly correct. For example, 2*7 is not an ugly number.
out of thin air you thought you should use 2,3,5 tables ? you should've explained what made you use that method instead of just explaining the code in English.
after a lot of practice, yes one will get ideas out of thin air.
Because ugly numbers are numbers whose prime factors are 2,3,5. Pretty straightforward.
Thank you for the explanation Bhaiya :)
But your intuitive solution is misleading. In your intuitive solution, you are basically taking a minimum number from tables of 2,3 and 5 at each iteration, by this approach, we will even have 14,21.... and so on as an ugly number which is incorrect.
Though, final dp approach is correct.
Yea I too realized it afterwards but can't change it now. I will try to put a new video for this if I get time and remove this one.
@@techdose4u hey could you explain what is the right intuition for DP?
@@techdose4u bro can you even discuss the top down approach for this
Why are 14 and 21 not ugly numbers though? 14 = 7 * 2. 2 is in the provided set. Same with 21 = 7 * 3.
Edit: I believe it's because it needs to have both factors be in the set. Both 14 and 21 each only have one in the set
The approach using something like bfs only to store it in a TreeSet so that they remain in an order and continuing until the interation reaches to can be something that works. But i dont think it involves dp.
Guys, this approach is wrong. Using a multiplication table means that at some point you will insert 14(2*7) or 21(3*7) and so on, which are not ugly numbers.
Hello, i need to write a programto find the 1500th ugly number, without any input. (C++) Could you help me out?
everyone is jumping straight to 2,3,5 tables to explain the solution. How did you arrive at the table?
because every number can only be divided by 2, 3, 5, one way to look at the sequence is to split the sequence to three groups as below:
(1) 1×2, 2×2, 3×2, 4×2, 5×2, …
(2) 1×3, 2×3, 3×3, 4×3, 5×3, …
(3) 1×5, 2×5, 3×5, 4×5, 5×5, …
We can find that every subsequence is the ugly-sequence itself (1, 2, 3, 4, 5, …) multiply 2, 3, 5. Then we use similar merge method as merge sort, to get every ugly number from the three subsequence. Every step we choose the smallest one, and move one step after.
@@assassinator3747 nice explanation ty👌👌👌👌
Great videos, Really Helpful .....Please keep up the great work !!
Thanks
Your method will give 14 as the ugly number, which is not. Please correct the error
In the code?
TECH DOSE your logic itself is wrong.
@@techdose4u The 2, 3, 5 tables method is wrong. If you continue further with that method, 14 will be an ugly number according to that logic.
how to write a recursive formula for this problem? because generally for all the dp problems I have been seeing some recursive formula, why not in this problem?
Have you found out the recursive approach?
Let me tell you this guy just copy the solution from one source and then make a video of them. I have the algorithm to generate ugly numbers which I wrote. I will paste it here.
@@swarnikagupta16
see the apprach is that for ugly number you have a choice to multiply it with 2,3 and 5. Each multiplication will give you an ugly number. so recursion node will be splitting into 3 more nodes.
Create an ugly number HashSet. Suppose you want to generate 100 ugly numbers. We will check if that ugly number is in the HashSet then we will not add it and will end the recursion process there. see this is a pseudo code solution so focus on the approach, not on syntax.
int N = 100; // total number of ugly numbers to generate.
Hashset hashset = new Hashset();
totalNumbersGenerated;
public void uglyGenerator(int num,int totalNumbersGenrated, int N, Hashset hashset){
if(hashSet.contains(num) || (totalNumbersGenerated==N))
{ return ; // this will help to terminate the multiple subproblems}
else if (hashSet.contains(num)!=true)
{ totalNumbersGenerated += 1;
hashset.add(num);
uglyGenerator(num*2);
uglyGenerator(num*3);
uglyGenerator(num*5);
}
}
But here is a problem in the solution. It will not generate the ugly numbers in sorted order.
solution should be explained as per exact "dp"-approach's intitution.
Excellent dp approach!!!!
Awesome bhaiya!!
Thanks :)
if the numbers are already present in the array then what should we do?
ex:-[1,2,3,4,5,6,8,9,10]
i1,i2,i3=10,9,10
then what should we do ?
from now it is getting wrong for me.
make a function for that let it be:- min(nm2,nm3,nm5) sor out of this 9 is min and it will return 9
It's wrong this time because it will give 14 also as ugly number but it is not!! Delete the video bro!!
bacha liye bhaiya
:)
How is brute force method tc is nlogn anyone pls explain
good explanation...thank you sir..
Welcome :)
thanks for such good explanation
Don't post wrong logic and waste our time
sare tutorial padh ke video banane aa jate hai bhai concept kaha hai
Best explanation
Thanks :)
Great video thank you so much man!!!!!
Great Explanation
can any one help why we are taking min only of those ?
we are going from bottom, so first we need to find i th ugly number before (i+1)th ugly number . Hence we are taking minimum of those
This approach is wrong. 7x2 = 14 This is not an ugly number
cool
👍
bhai code chala kr bhi dikha diya kro
Wrong Algo!!!!!!!
bhai galat approach hai ye
the algo is wrong.unsuscribing the channel