✅☑️ Best C++ 3 Solution || DP || Tabulation || Hash Table || Math || One Stop Solution.
Intuition\n Describe your first thoughts on how to solve this problem. \nWe can solve this question using Multiple Approaches. (Here I have explained all the po
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe can solve this question using Multiple Approaches. (Here I have explained all the possible solutions of this problem).\n\n1. Solved using Math.\n2. Solved using Hash Table.\n3. Solved using Dynamic Programming (Tabulation).\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe can easily understand the all the approaches by seeing the code which is easy to understand with comments.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nTime complexity is given in code comment.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nSpace complexity is given in code comment.\n\n# Code\n```\n/*\n\n    Time Complexity : O(K) where K is the nth ugly number. Beacuse we are traversing the loop K times so, the\n    time complexity is O(K).\n\n    Space Complexity : O(1), Constant space.\n\n    Solved using Math.\n\n    Note : This approach will give TLE.\n\n*/\n\n\n/***************************************** Approach 1 *****************************************/\n\nclass Solution {\nprivate:\n    int keepsOndividingUntilPossible(int dividend, int divisor){\n        while(dividend % divisor == 0){\n            dividend /= divisor;\n        }\n        return dividend;\n    }\npublic:\n    int nthUglyNumber(int n) {\n        int i=0, count=0;\n        while(count < n){\n            int isUgly = i+1;\n            for(auto factor : {2,3,5}){\n                isUgly = keepsOndividingUntilPossible(isUgly, factor);\n            }\n            if(isUgly == 1){\n                count++;\n            }\n            i++;\n        }\n        return i;\n    }\n};\n\n\n\n\n\n\n/*\n\n    Time Complexity : O(NlogN), The time complexity of the code is O(NlogN) since we are doing 3 insertion\n    operation in Hash Table(set) for each iteration in loop N times and insertion operation in Hash Table(set) \n    takes logN time. Where N is the given number n.\n\n    Space Complexity : O(N), Hash Table(set) space.\n\n    Solved using Hash Table.\n\n*/\n\n\n/***************************************** Approach 2 *****************************************/\n\nclass Solution {\npublic:\n    int nthUglyNumber(int n) {\n        set<long> set;\n        long nthNumber = 1;\n        set.insert(nthNumber);\n        for(int i=0; i<n; i++){\n            nthNumber = *set.begin();\n            set.erase(nthNumber);\n            set.insert(nthNumber*2);\n            set.insert(nthNumber*3);\n            set.insert(nthNumber*5);\n        }\n        return nthNumber;\n    }\n};\n\n\n\n\n\n\n/*\n\n    Time Complexity : O(N), Here loop creates the time Complexity. Where N is the given number n.\n\n    Space Complexity : O(N), Array(dp) space.\n\n    Solved using Dynamic Programming (Tabulation).\n\n*/\n\n\n/***************************************** Approach 3 *****************************************/\n\nclass Solution {\npublic:\n    int nthUglyNumber(int n) {\n        vector<int> dp(n);\n        dp[0]=1;\n        int x=0, y=0, z=0;\n        for(int i=1; i<n; i++){\n            dp[i] = min(dp[x]*2, min(dp[y]*3, dp[z]*5));\n            if(dp[i] == 2*dp[x]) x++;\n            if(dp[i] == 3*dp[y]) y++;\n            if(dp[i] == 5*dp[z]) z++;\n        }\n        return dp[n-1];\n    }\n};\n\n```\n\n***IF YOU LIKE THE SOLUTION THEN PLEASE UPVOTE MY SOLUTION BECAUSE IT GIVES ME MOTIVATION TO REGULARLY POST THE SOLUTION.***\n\n![WhatsApp Image 2023-02-10 at 19.01.02.jpeg](https://assets.leetcode.com/users/images/0a95fea4-64f4-4502-82aa-41db6d77c05c_1676054939.8270252.jpeg)
['Hash Table', 'Math', 'Dynamic Programming', 'C++']