Super Ugly Number

LeetCode Q 313 - Super Ugly Number

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 primes of size k.

Solution

Code:

public int nthSuperUglyNumber(int n, int[] primes) {
	int[] times = new int[primes.length];
	int[] uglys = new int[n];
	uglys[0] = 1;

	for (int i = 1; i < n; i++) {
		uglys[i] = Integer.MAX_VALUE;

		for (int j = 0; j < primes.length; j++) 
			uglys[i] = Math.min(uglys[i], primes[j] * uglys[times[j]]);
		
		for (int j = 0; j < times.lnegth; j++)
			if (uglys[times[j]] * primes[j] == uglys[i])
				times[j]++;
	}

	return ugly[n - 1];
}

Code: Heap + Set

public int nthSuperUglyNumber(int n, int[] primes) {
	PriorityQueue<Long> que = new PriorityQueue<>();
	Set<Long> set = new HashSet<>();
	que.offer(1L); set.add(1L);
	for (int i = 1; i < n; i++) {
		long num = que.poll();
		for (int prime: primes) {
			if (set.add(prime * num))
				que.offer(prime * num);
		}
	}
	return que.poll().intValue(); // need to convert it into int
}