Ugly Number question giving wrong answer.
Ugly Numbers Wrong Answer
@sanidhyasamadhiya Here the value of n is 10000, but the nth ugly number can be very large, as you have considered till dp[100002] it will limit it till that only. Check it by taking input around 1000, it will output 0
As we know that every ugly number is made up of 2,3 or 5. So we will just start building it from 1.
So the ugly numbers will be from these sequences:-
(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, …
See for reducing space complexity, you just need to maintain three variables which will denote the next_2_multiple, next_3_multiple, next_5_multiple.
and at every step compare them and the minimum among them will be ith ugly number. At same time update that variable which is minimum, like for eg if next_5_multiple is smallest among them.
then just assign ith ugly number to that and at same time update next_5_multiple.
for keeping track of multiples of 2, 3 and 5. Use seperate variables i2, i3, and i5 which will point to last the multiple which was selected as ugly number.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.