Beats 100% | bottom up easy approach | vid explanation
Vid Explanation\nhttps://youtu.be/ge1YaItnLiI\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \n- Ugly numbers are numbers whose pri
# Vid Explanation\nhttps://youtu.be/ge1YaItnLiI\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Ugly numbers are numbers whose prime factors are limited to 2, 3, and 5.\n- The nth ugly number can be obtained by multiplying a previous ugly number by 2, 3, or 5.\n- We can efficiently generate ugly numbers by keeping track of the smallest possible multiplications of existing ugly numbers by 2, 3, and 5.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Create a dynamic programming array dp to store the ugly numbers. Initialize dp[0] to 1.\n- Maintain three pointers p1, p2, and p3 to track the indices of the next ugly number to be multiplied by 2, 3, and 5 respectively.\n- Iterate through the dp array:\n- Calculate the potential next ugly numbers by multiplying dp[p1] by 2, dp[p2] by 3, and dp[p3] by 5.\n- Find the minimum of these three values and store it as the next ugly number in dp.\n- Increment the corresponding pointer (p1, p2, or p3) based on which value was chosen.\n- Return the last element of the dp array, which is the nth ugly number.\n\n# Complexity\n- Time complexity:O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int nthUglyNumber(int n) {\n\n        vector<int> dp(n);\n        dp[0] = 1;\n\n        int p1 = 0;\n        int p2 = 0;\n        int p3 = 0;\n\n        for(int i=1;i<n;i++){\n\n            int twoMul = dp[p1] * 2;\n            int threeMul = dp[p2] * 3;\n            int fiveMul = dp[p3] * 5;\n\n            dp[i] = min(twoMul, min(threeMul,fiveMul ));\n\n            if(dp[i] == twoMul) p1++;\n            if(dp[i] == threeMul) p2++;\n            if(dp[i] ==  fiveMul) p3++;\n            \n        }\n\n        return dp[n-1];\n        \n    }\n};\n```
['C++']