Wrong answer in Ugly Numbers

#1

My sample test cases are working but I’m getting a wrong answer when I submit the code.

#2

your logic is wrong.


you can see this.

1 Like
#3

Ugly number(i) = minimum of (2 * ugly number(f2), 3* ugly number(f3), 5*ugly number(f5))

Where, f2, f3, f5 are counters for 2, 3, 5 respectively which stores the index for f2th ugly number, f3th ugly number, f5th ugly number.

Then we will store our answer.

Algorithm:

Initializing f2, f3, f5 to maintain f2th ugly number, f3th ugly number and f5th ugly number to 1.
Creating a DP matrix in which ith cell represent ith ugly number.
Start filling the dp matrix from i = 2.
Ugly number(i) = minimum of (2 * ugly number(f2), 3* ugly number(f3), 5*ugly number(f5)).
Finding the answer using above relation and storing it at ith index.
Now, the time complexity of the above code is O(N).

1 Like
#4

Please mark your doubts as resolved in your course’s. and please rate your experience here