Optimal C, Java, C++, PHP Solution with 100% Runtime Efficiency || With explanation  🔥🔥💯💯
\n\n\n# Approach\n Describe your approach to solving the problem. \n - Three Pointers (i2, i3, i5): These pointers track the indices for the next multiples of 2
![Screenshot 2024-08-18 073257.png](https://assets.leetcode.com/users/images/4351a0a8-01a1-4a37-ad1c-caf12f5c8f25_1723946762.3377025.png)\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n - Three Pointers (i2, i3, i5): These pointers track the indices for the next multiples of 2, 3, and 5.\n - Ugly Array: Stores the sequence of ugly numbers.\n - Next Values: next2, next3, and next5 store the next possible ugly number derived by multiplying by 2, 3, and 5, respectively.\n - Efficiency: The solution ensures that every ugly number is generated in order by incrementing the appropriate pointer whenever a new ugly number is added to the sequence. This avoids generating duplicates and ensures minimal operations.\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```cpp []\nclass Solution {\npublic:\n    int nthUglyNumber(int n) {\n        vector<int> ugly(n);\n        ugly[0] = 1;\n        int i2 = 0, i3 = 0, i5 = 0;\n        int next2 = 2, next3 = 3, next5 = 5;\n\n        for (int i = 1; i < n; i++) {\n            int nextUgly = min(next2, min(next3, next5));\n            ugly[i] = nextUgly;\n\n            if (nextUgly == next2) {\n                i2++;\n                next2 = ugly[i2] * 2;\n            }\n            if (nextUgly == next3) {\n                i3++;\n                next3 = ugly[i3] * 3;\n            }\n            if (nextUgly == next5) {\n                i5++;\n                next5 = ugly[i5] * 5;\n            }\n        }\n\n        return ugly[n - 1];\n    }\n};\n\n```\n```java []\nclass Solution {\n    public int nthUglyNumber(int n) {\n        int[] ugly = new int[n];\n        ugly[0] = 1;\n        int i2 = 0, i3 = 0, i5 = 0;\n        int next2 = 2, next3 = 3, next5 = 5;\n\n        for (int i = 1; i < n; i++) {\n            int nextUgly = Math.min(next2, Math.min(next3, next5));\n            ugly[i] = nextUgly;\n\n            if (nextUgly == next2) {\n                i2++;\n                next2 = ugly[i2] * 2;\n            }\n            if (nextUgly == next3) {\n                i3++;\n                next3 = ugly[i3] * 3;\n            }\n            if (nextUgly == next5) {\n                i5++;\n                next5 = ugly[i5] * 5;\n            }\n        }\n\n        return ugly[n - 1];\n    }\n}\n```\n```python3 []\nclass Solution:\n    def nthUglyNumber(self, n: int) -> int:\n        ugly = [0] * n\n        ugly[0] = 1\n        i2 = i3 = i5 = 0\n        next2, next3, next5 = 2, 3, 5\n\n        for i in range(1, n):\n            nextUgly = min(next2, next3, next5)\n            ugly[i] = nextUgly\n\n            if nextUgly == next2:\n                i2 += 1\n                next2 = ugly[i2] * 2\n            if nextUgly == next3:\n                i3 += 1\n                next3 = ugly[i3] * 3\n            if nextUgly == next5:\n                i5 += 1\n                next5 = ugly[i5] * 5\n\n        return ugly[n - 1]\n```\n```c []\nint min(int a, int b, int c) {\n    if (a < b) {\n        return (a < c) ? a : c;\n    } else {\n        return (b < c) ? b : c;\n    }\n}\n\nint nthUglyNumber(int n) {\n    int *ugly = (int*)malloc(n * sizeof(int));\n    ugly[0] = 1;\n    int i2 = 0, i3 = 0, i5 = 0;\n    int next2 = 2, next3 = 3, next5 = 5;\n\n    for (int i = 1; i < n; i++) {\n        int nextUgly = min(next2, next3, next5);\n        ugly[i] = nextUgly;\n\n        if (nextUgly == next2) {\n            i2++;\n            next2 = ugly[i2] * 2;\n        }\n        if (nextUgly == next3) {\n            i3++;\n            next3 = ugly[i3] * 3;\n        }\n        if (nextUgly == next5) {\n            i5++;\n            next5 = ugly[i5] * 5;\n        }\n    }\n\n    int result = ugly[n - 1];\n    free(ugly);\n    return result;\n}\n```\n\n\n```javascript []\nvar nthUglyNumber = function(n) {\n    let ugly = new Array(n);\n    ugly[0] = 1;\n    let i2 = 0, i3 = 0, i5 = 0;\n    let next2 = 2, next3 = 3, next5 = 5;\n\n    for (let i = 1; i < n; i++) {\n        let nextUgly = Math.min(next2, Math.min(next3, next5));\n        ugly[i] = nextUgly;\n\n        if (nextUgly === next2) {\n            i2++;\n            next2 = ugly[i2] * 2;\n        }\n        if (nextUgly === next3) {\n            i3++;\n            next3 = ugly[i3] * 3;\n        }\n        if (nextUgly === next5) {\n            i5++;\n            next5 = ugly[i5] * 5;\n        }\n    }\n\n    return ugly[n - 1];\n};\n```\n```php []\nclass Solution {\n    function nthUglyNumber($n) {\n        $ugly = array_fill(0, $n, 0);\n        $ugly[0] = 1;\n        $i2 = 0; $i3 = 0; $i5 = 0;\n        $next2 = 2; $next3 = 3; $next5 = 5;\n\n        for ($i = 1; $i < $n; $i++) {\n            $nextUgly = min($next2, min($next3, $next5));\n            $ugly[$i] = $nextUgly;\n\n            if ($nextUgly == $next2) {\n                $i2++;\n                $next2 = $ugly[$i2] * 2;\n            }\n            if ($nextUgly == $next3) {\n                $i3++;\n                $next3 = $ugly[$i3] * 3;\n            }\n            if ($nextUgly == $next5) {\n                $i5++;\n                $next5 = $ugly[$i5] * 5;\n            }\n        }\n\n        return $ugly[$n - 1];\n    }\n}\n\n```\n```kotlin []\nclass Solution {\n    fun nthUglyNumber(n: Int): Int {\n        val ugly = IntArray(n)\n        ugly[0] = 1\n        var i2 = 0\n        var i3 = 0\n        var i5 = 0\n        var next2 = 2\n        var next3 = 3\n        var next5 = 5\n\n        for (i in 1 until n) {\n            val nextUgly = minOf(next2, next3, next5)\n            ugly[i] = nextUgly\n\n            if (nextUgly == next2) {\n                i2++\n                next2 = ugly[i2] * 2\n            }\n            if (nextUgly == next3) {\n                i3++\n                next3 = ugly[i3] * 3\n            }\n            if (nextUgly == next5) {\n                i5++\n                next5 = ugly[i5] * 5\n            }\n        }\n\n        return ugly[n - 1]\n    }\n}\n\n```\n\n
['Hash Table', 'Math', 'C', 'PHP', 'C++', 'Java', 'Python3', 'Kotlin', 'JavaScript']