int min(int x,int y,int z)
{
    int t = 0;
    if(x<y)t = x;
    else t = y;
    if(t>z) t = z;
    return t;
}

int nthUglyNumber(int n){
    long* data = (long*)malloc(sizeof(long)*(n+1));
    data[0] = 1;
    int index = 0;
    int p2 = 0;
    int p3 = 0;
    int p5 = 0;
    while(index < n)
    {
        index++;
        long d = min(data[p2]*2,data[p3]*3,data[p5]*5);
        data[index] = d;
        while(data[p2]*2 == data[index])
        {
            p2++;
        }
         while(data[p3]*3 == data[index])
        {
            p3++;
        }
         while(data[p5]*5 == data[index])
        {
            p5++;
        }
    }
    return data[n-1];
}