✅Easy and Simple Solution | ✅ Dp concept | ✅ cpp
Intuition\n Describe your first thoughts on how to solve this problem. \nTo find the nth ugly number, the key idea is to generate ugly numbers sequentially by m
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo find the `n`th ugly number, the key idea is to generate ugly numbers sequentially by maintaining the smallest possible multiples of 2, 3, and 5 from previously generated ugly numbers. Starting with 1 (the first ugly number), you track and update the next candidates for ugly numbers by multiplying existing ones by 2, 3, and 5, always choosing the smallest available option to ensure the sequence is in order. This approach efficiently builds the list of ugly numbers until the `n`th one is reached, ensuring that every number in the sequence only has 2, 3, and 5 as its prime factors.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(N)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(N)\n# Code\n```\nclass Solution {\npublic:\n    int nthUglyNumber(int n) {\n        if (n <= 0) return 0;\n\n        vector<int> uglyNumbers(n);\n        uglyNumbers[0] = 1;  // The first ugly number is 1.\n        \n        int i2 = 0, i3 = 0, i5 = 0; // Indices for multiples of 2, 3, and 5\n        int nextMultipleOf2 = 2;\n        int nextMultipleOf3 = 3;\n        int nextMultipleOf5 = 5;\n\n        for (int i = 1; i < n; i++) {\n            int nextUglyNumber = min(nextMultipleOf2, min(nextMultipleOf3, nextMultipleOf5));\n            uglyNumbers[i] = nextUglyNumber;\n\n            if (nextUglyNumber == nextMultipleOf2) {\n                i2++;\n                nextMultipleOf2 = uglyNumbers[i2] * 2;\n            }\n            if (nextUglyNumber == nextMultipleOf3) {\n                i3++;\n                nextMultipleOf3 = uglyNumbers[i3] * 3;\n            }\n            if (nextUglyNumber == nextMultipleOf5) {\n                i5++;\n                nextMultipleOf5 = uglyNumbers[i5] * 5;\n            }\n        }\n\n        return uglyNumbers[n - 1];\n    }\n};\n\n```\n![upvote_pic.webp](https://assets.leetcode.com/users/images/c5f0478a-1a55-4bfd-b548-06b7b798c148_1723960710.3305547.webp)\n
['C++']