🤖 leetcode 264. Ugly Number II | medium | prime-number | javascript

🗒️ Problems

264. Ugly Number II - Leetcode

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return the nth ugly number.

Input: n = 10
Output: 12
Explanation: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers.

🤦‍♂️ First attempt

• I got prime factoring template.
• Given a number, find prime factors and check whether they are limited to 2, 3, and 5.
• But, I got TLE.

var nthUglyNumber = function (n) {
  const primeFactors = (n) => {
    let counts = {};
    for (let x = 2; x * x <= n; x++) {
      while (n % x === 0) {
        counts[x] = (counts[x] || 0) + 1;
        n /= x;
      }
    }
    if (n > 1) counts[n] = (counts[n] || 0) + 1;
    return counts;
  };

  const res = Array(n).fill(-1);
  res[0] = 1;

  let num = 2;
  let i = 1;

  while (i < n) {
    const primes = Object.keys(primeFactors(num)).map(Number);
    if (primes.every((prime) => prime === 2 || prime === 3 || prime === 5)) {
      res[i] = num;
      i += 1;
    }
    num += 1;
  }
  return res[n - 1];
};

🥳 Think differently

• Check the definition again: An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.
• This means that new ugly number is generated by multiplying the previous ugly number with 2, 3 and 5.
• Can we choose the next ugly number using minHeap ?

🔥 My Solution

/**
 * @param {number} n
 * @return {number}
 */
var nthUglyNumber = function (n) {
  const minHeap = new MinPriorityQueue({ compare: (a, b) => a - b });
  minHeap.enqueue(1);

  const res = [];
  const set = new Set();

  while (res.length < n) {
    const min = minHeap.dequeue();
    if (set.has(min)) continue;

    res.push(min);
    set.add(min);

    minHeap.enqueue(min * 2);
    minHeap.enqueue(min * 3);
    minHeap.enqueue(min * 5);
  }

  return res[n - 1];
};