Ugly numbers from dp

#1

Here’s my implementation of ugly numbers. I am doing it using sieve, if a current number is a prime number I am not including that in our sequence but keeping 2,3,5 as my exception. I am getting segmentation fault here. Please help

#2

hello @div_yanshu07

the segfault is due to overflow.
image

use long long here.

also the approach is not correct.
u are just avoiding prime numbers but there can be composite number which is not ugly number.

try different approach

#3

see this->
We have an array k of first n ugly number. We only know, at the beginning, the first one, which is 1. Then

k[1] = min( k[0]x2, k[0]x3, k[0]x5). The answer is k[0]x2. So we move 2’s pointer to 1. Then we test:

k[2] = min( k[1]x2, k[0]x3, k[0]x5). And so on. Be careful about the cases such as 6, in which we need to forward both pointers of 2 and 3.

  int nthUglyNumber(int n) {
        if(n <= 0) return false; // get rid of corner cases 
        if(n == 1) return true; // base case
        int t2 = 0, t3 = 0, t5 = 0; //pointers for 2, 3, 5
        vector<int> k(n);
        k[0] = 1;
        for(int i  = 1; i < n ; i ++)
        {
            k[i] = min(k[t2]*2,min(k[t3]*3,k[t5]*5));
            if(k[i] == k[t2]*2) t2++; 
            if(k[i] == k[t3]*3) t3++;
            if(k[i] == k[t5]*5) t5++;
        }
        return k[n-1];
    }
#4

Array of first k ugly numbers?? HOW??

#5

bro by that i mean we have array k with size n .

and in that array only first element is known i.e 1
and then we have to find remaining k-1 or n-1 remaining entries

#6

Okay, I understood the code but can explain what was the logic behind this approach??

#7

you*…

#9

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.