Java Solution | Fast | 2 solutions
Same as Ugly Number II (https://leetcode.com/problems/ugly-number-ii/) :\ndifference is that there 2,3,5 are given as primes[]\nhere array is given!\nSolution o
Same as Ugly Number II ([https://leetcode.com/problems/ugly-number-ii/](http://)) :\ndifference is that there 2,3,5 are given as primes[]\nhere array is given!\nSolution of Ugly Number II ->\n```\npublic int dp[]; //global variable\n    public int nthUglyNumber(int n) {\n         dp=new int[n];\n        int a=0,b=0,c=0;\n        dp[0]=1;\n        for(int i=1;i<n;i++) {\n            int two=dp[a]*2;\n            int three=dp[b]*3;\n            int five=dp[c]*5;\n            \n            int min=Math.min(two,Math.min(three,five));\n            \n            if(min==two) a++;\n            if(min==three) b++;\n            if(min==five) c++;\n            \n            dp[i]=min;\n        }\n        return dp[n-1];\n    }\n```\n\nNow in this question two approaches are given first one is same is the discussed above and the second is optimisation\nover first using PriorityQueue!\n First Approach: Time-O(n*k) where k is no. of primes and n is the nth no. to be found\n ```\n public int nthSuperUglyNumber(int n, int[] primes) {\n        int dp[]=new int[n];\n        dp[0]=1;\n        \n        int indexes[]=new int[primes.length]; //indexes of different no. in prime\n        for(int i=1;i<n;i++) {\n            int min=dp[indexes[0]]*primes[0];\n            for(int j=1;j<primes.length;j++) {\n                if(min>dp[indexes[j]]*primes[j]) {\n                    min=dp[indexes[j]]*primes[j];\n                }\n            }\n            \n            for(int j=0;j<primes.length;j++) {\n                if(min==dp[indexes[j]]*primes[j])\n                    indexes[j]++;       \n            }\n            \n            dp[i]=min;\n        }\n        // System.out.println(Arrays.toString(dp));\n        return dp[n-1];\n    }\n ```\n \n Second Approach: optimisation over the first one!\n Time-O(n*log(k))\n ```\n class Solution {\n    public int nthSuperUglyNumber(int n, int[] primes) {\n        //OPTIMISED APPROACH USING PRIORITY QUEUE \n        //above method\'s optimisation\n        int dp[]=new int[n];\n        dp[0]=1;\n        int i=1;\n        \n        \n        Queue<Pair> pq=new PriorityQueue<>();\n        //initising priority queue\n        for(int j=0;j<primes.length;j++)\n            pq.add(new Pair(0,primes[j],dp[0]*primes[j]));\n        \n        while(i<n) {\n            Pair p=pq.remove();\n            if(dp[i-1]!=p.value) {\n                dp[i]=p.value;\n                i++;\n            }\n            p.index++;\n            p.value=dp[p.index]*p.prime;\n            pq.add(p);\n        }\n        // System.out.println(Arrays.toString(dp));\n        return dp[n-1];\n    }\n    \n    public static class Pair implements Comparable<Pair>{\n        int index;\n        int prime;\n        int value;\n            \n        Pair(int index,int prime,int value) {\n            this.index=index;\n            this.prime=prime;\n            this.value=value;\n        }\n            \n        public int compareTo(Pair second) {\n            return this.value-second.value;\n        }\n    }\n}\n ```
['Dynamic Programming', 'Heap (Priority Queue)']