Leetcode[313] Super Ugly Number
10 Dec 2015###Task1 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. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.
Note:
(1) 1 is a super ugly number for any given primes.
(2) The given numbers in primes are in ascending order.
(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.
###Java ####TLE
public class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
if (primes == null || primes.length == 0 || n == 1) {
return 1;
}
ArrayList<Integer> list = new ArrayList<>();
ArrayList<Integer> res = new ArrayList<>();
list.add(1);
for (int i: primes) {
list.add(i);
}
while (res.size() < n) {
int min = Integer.MAX_VALUE;
for (int i = 0; i < list.size(); i++) {
int cur = list.get(i);
for (int j = 0; j < list.size(); j++) {
if (!res.contains(cur * list.get(j))) {
min = Math.min(min, cur * list.get(j));
}
}
}
res.add(min);
list.add(min);
}
return res.get(n - 1);
}
}
###O(kn)
public class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
int len = primes.length;
int[] index = new int[len]; //index[0]==0, ... index[len-1]==0
int[] res = new int[n];
res[0] = 1;
for(int i=1; i<n; i++) {
int min = Integer.MAX_VALUE;
for(int j=0; j<len; j++){
min = Math.min(res[index[j]]*primes[j], min);
}
res[i] = min;
for (int j=0; j<len; j++) {
if(res[i]%primes[j]==0) index[j]++;
}
}
return res[n-1];
}
}
###Points
- Exactly like Ugly Number II.
- How to generate the next one in res array? Let every single num in primes times the result inside res array. But TLE make extra efforts. We can mark their index to reduce the work.