1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
// 313. Super Ugly Number
#include "leetcode.h"
/*
* a super ugly number is a positive integer whose prime factors are in the
* array 'primes'. given an integer 'n' and an array of integers 'primes',
* return the n'th super ugly number. the n'th super ugly number is guaranteed
* to fit in a 32-bit integer (signed)
*/
int nthSuperUglyNumber(int n, int *primes, int primes_size) {
int *idx = (int *)calloc(primes_size, sizeof(int));
int *nums = (int *)malloc(sizeof(int) * n);
*nums = 1;
for (int i = 1; i < n; ++i) {
int min = INT_MAX;
for (int j = 0; j < primes_size; ++j)
min = fmin(min, nums[idx[j]] * primes[j]); // INT_MAX overflows fmin here
nums[i] = min;
for (int j = 0; j < primes_size; ++j)
if (nums[idx[j]] * primes[j] == min)
++idx[j];
}
return nums[n - 1];
}
int main() {
int p1[] = {2, 7, 13, 19}, p2[] = {2, 3, 5};
printf("%d\n", nthSuperUglyNumber(12, p1, ARRAY_SIZE(p1))); // expect: 32
printf("%d\n", nthSuperUglyNumber(1, p2, ARRAY_SIZE(p2))); // expect: 1
}
|