Efficient Ugly Number Generation
Intuition\nUgly numbers are those numbers whose only prime factors are 2, 3, or 5. The first ugly number is 1. All other ugly numbers can be generated by multip
# Intuition\nUgly numbers are those numbers whose only prime factors are 2, 3, or 5. The first ugly number is 1. All other ugly numbers can be generated by multiplying existing ugly numbers by 2, 3, or 5.\n\n\n# Approach\n1. Initialization:A vector v of size n is used to store the generated ugly numbers.\n    The first element of the vector v[0] is set to 1, as 1 is considered the first ugly number.\n    Three variables a, b, and c are initialized to 0, representing indices to track the multiples of 2, 3, and 5 respectively.\n\n2. Generating Ugly Numbers Iteratively:Starting from i = 1, the loop iterates until i < n.\n\n3. Within each iteration:The next ugly number is calculated by taking the minimum among the products of the current numbers at indices a, b, and c with 2, 3, and 5 respectively.\n    This minimum value is assigned to v[i], the ith element of the vector.\n    The indices a, b, and c are updated based on which number contributed to the minimum value.\n\n4. Updating Indices:If the next ugly number was produced by multiplying the number at index a by 2, then a is incremented.\nThe same logic applies to b and c.\n\n5. Returning the Result:Once all n ugly numbers are generated, the last element of the vector v (i.e., v[n-1]) is returned as the nth ugly number.\n\n# Complexity\n- Time complexity:\nO(n) \n\n- Space complexity:\nO(n) \n\n# Code\n```\nclass Solution {\npublic:\n    int nthUglyNumber(int n) {\n        //1,2,3,4,5,6,8,9,10,12,15...\n\n        if(n<=0)\n        {\n            return 0;\n        }\n\n        vector<int>v(n);\n        //first num is 1\n        v[0]=1;\n\n        int a=0; //multiple of 2\n        int b=0; //multiple of 3\n        int c=0; //multiple of 5\n\n        for(int i=1;i<n;i++)\n        {\n            //finding smallest multiple\n            int num=min({v[a]*2,v[b]*3,v[c]*5});\n            //int num=min((v[a]*2,v[b]*3),v[c]*5);\n            v[i]=num;\n\n            if(num==v[a]*2)\n            {\n                a++;\n            }\n            if(num==v[b]*3)\n            {\n                b++;\n            }\n            if(num==v[c]*5)\n            {\n                c++;\n            }\n        }\n        return v[n-1];\n\n    }\n};\n```
['Math', 'C++']