leetcode-javascript/solutions/0313-super-ugly-number.js at development · Anuj9826/leetcode-javascript · GitHub

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
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Super Ugly Number
 * Time Complexity: O(N * K)
 * Space Complexity: O(N + K)
 */
var nthSuperUglyNumber = function (n, primes) {
  const superUglyValues = [1];
  const primeIndices = new Array(primes.length).fill(0);
  const candidateProducts = [...primes];

  let currentCount = superUglyValues.length;

  while (currentCount < n) {
    let minimumCandidate = Infinity;
    for (
      let currentProductIndex = 0;
      currentProductIndex < candidateProducts.length;
      currentProductIndex++
    ) {
      if (candidateProducts[currentProductIndex] < minimumCandidate) {
        minimumCandidate = candidateProducts[currentProductIndex];
      }
    }

    superUglyValues.push(minimumCandidate);

    for (
      let primeFactorIndex = 0;
      primeFactorIndex < primes.length;
      primeFactorIndex++
    ) {
      if (candidateProducts[primeFactorIndex] === minimumCandidate) {
        primeIndices[primeFactorIndex]++;
        candidateProducts[primeFactorIndex] =
          primes[primeFactorIndex] *
          superUglyValues[primeIndices[primeFactorIndex]];
      }
    }
    currentCount++;
  }

  return superUglyValues[n - 1];
};