Nth Super Ugly Number

Problem: Write a program to find the nth super ugly number. Super ugly numbers are positive numbers whose all prime factors are in the given prime list of size k.

Example:

Input: n = 5, primes = [2,7]
Output: 8 
Explanation: [1,2,4,7,8] is the sequence of the first 5 super ugly numbers given primes = [2,7].

Approach: The approach will be same as finding Nth Ugly Number. Here the primes are given in an array where as in the previous problem we have only 2, 3 and 5 as primes. You can understand it by just looking at the implementation and the approach of the previous problem.

Implementation in C#:

        public static int NthSuperUglyNumber(int n, int[] primes)

        {

            if (n == 0)

            {

                return 0;

            }

            List<int> table = new List<int> { 1 };

            int[] primesCount = new int[primes.Length];

            for (int i = 0; i < n - 1; ++i)

            {

                table.Add(NextSuperUglyNumber(table, primes, primesCount));

            }

            return table.Last();

        }

        private static int NextSuperUglyNumber(List<int> table, int[] primes, int[] primesCount)

        {

            int nextSuperUglyNumber = int.MaxValue;

            for (int i = 0; i < primes.Length; ++i)

            {

                nextSuperUglyNumber = Math.Min(nextSuperUglyNumber, primes[i] * table[primesCount[i]]);

            }

            for (int i = 0; i < primes.Length; ++i)

            {

               if (nextSuperUglyNumber == primes[i] * table[primesCount[i]])

                {

                    ++primesCount[i];

                }

            }

            return nextSuperUglyNumber;

        }

Complexity: O( n* m) where m is the size of primes array