✅ 💡Most efficient C++ approach using DP
Intuition\nThe solution uses dynamic programming to find the nth ugly number. It initializes a vector "dp" of size n and sets the first element to 1 since 1 is 
# Intuition\nThe solution uses dynamic programming to find the nth ugly number. It initializes a vector "dp" of size n and sets the first element to 1 since 1 is considered an ugly number. Three pointers are used to keep track of the multiples of 2, 3, and 5. Initially, all pointers are set to 0.\n\nIn each iteration of the loop, the algorithm computes the next ugly number by taking the minimum of the next possible multiples of 2, 3, and 5 using the values at the corresponding pointer positions. The resulting minimum is stored in the dp array at the current index. If any of the pointers generate an equal value to the computed ugly number, then that pointer is incremented.\n\nBy the end of the loop, the nth ugly number would be found in the last position of the dp array, so this value is returned.\n\nIntuitively, this solution works because it generates all possible ugly numbers in ascending order up to the nth ugly number. Since we are using dynamic programming to store previously computed values, we avoid recomputing already calculated values, thus reducing the time complexity of the algorithm.\n\n# Approach\nSure, here\'s a step-by-step explanation of the algorithm:\n\n- Create a vector "dp" of size n to store the first n ugly numbers.\n\n- Set the first element of dp to 1 since 1 is considered an ugly number.\n\n- Initialize three pointers: ptr1, ptr2, and ptr3 to keep track of multiples of 2, 3, and 5 respectively. All these pointers are initially set to 0.\n\n- In each iteration of the loop starting from i = 1, compute the next possible multiple of 2, 3, and 5 by multiplying the value at dp[ptr1], dp[ptr2], and dp[ptr3] with 2, 3, and 5 respectively. Let these values be stored in variables multipleOfTwo, multipleOfThree, and multipleOfFive respectively.\n\n- The minimum value among these three computed multiples of 2, 3, and 5 is the next ugly number in the sequence. Store this minimum value in dp[i].\n\n- If the computed ugly number is equal to multipleOfTwo, increment ptr1.\n\n- If the computed ugly number is equal to multipleOfThree, increment ptr2.\n\n- If the computed ugly number is equal to multipleOfFive, increment ptr3.\n\n- Repeat the steps 4-8 until we have generated the nth ugly number.\n\n- Return the last element of dp, which is the nth ugly number.\n\nBy following these steps, the algorithm will generate all possible ugly numbers up to the nth ugly number while avoiding recomputing already calculated values, thus reducing the time complexity of the algorithm.\n\n# Complexity\n- Time complexity: $$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        vector<int> dp(n);\n        dp[0] = 1;\n        int ptr1 = 0, ptr2 = 0, ptr3 = 0;\n\n        for(int i = 1; i < n; i++){\n          int multipleOfTwo = dp[ptr1] * 2;\n          int multipleOfThree = dp[ptr2] * 3;\n          int multipleOfFive = dp[ptr3] * 5;\n\n          dp[i] = min(multipleOfTwo, min(multipleOfThree, multipleOfFive));\n\n          if(multipleOfTwo == dp[i]){\n            ptr1++;\n          }\n          if(multipleOfThree == dp[i]){\n            ptr2++;\n          }\n          if(multipleOfFive == dp[i]){\n            ptr3++;\n          }\n        }\n\n        return dp[n - 1];\n    }\n};\n```
['Dynamic Programming', 'C++']