Super Ugly Number

Description

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.

Example:

Input: n = 12, primes = [2,7,13,19]
Output: 32 
Explanation: [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 is a super ugly number for any given primes.
• The given numbers in primes are in ascending order.
• 0 < k ≤ 100, 0 < n ≤ 10⁶, 0 < primes[i] < 1000.
• The n^th super ugly number is guaranteed to fit in a 32-bit signed integer.

Solution(javascript)

// // O(kn) time
// const nthSuperUglyNumber = (n, primes = []) => {
//   const result = [1]
//   const indexes = primes.map(() => 0)
//   while (result.length < n) {
//     const numbers = indexes.map((index, arrIndex) => result[index] * primes[arrIndex])
//     const min = Math.min(...numbers)

//     const minIndex = numbers.findIndex(num => num === min)
//     indexes[minIndex] += 1
//     if (min !== result[result.length - 1]) {
//       result.push(min)
//     }
//   }
//   return result[n - 1]
// }

class Heap {
  constructor(list, compare = (a, b) => a - b) {
    this.left = index => 2 * index + 1
    this.right = index => 2 * index + 2
    this.parent = index => Math.floor((index - 1) / 2)
    this.heapify = (index = 0) => {
      const { list } = this
      const leftIndex = this.left(index)
      const rightIndex = this.right(index)
      let maxIndex = index
      if (list[leftIndex] !== undefined
        && this.compare(list[maxIndex], list[leftIndex]) > 0) {
        maxIndex = leftIndex
      }
      if (list[rightIndex] !== undefined
        && this.compare(list[maxIndex], list[rightIndex]) > 0) {
        maxIndex = rightIndex
      }
      if (index !== maxIndex) {
        const temp = list[index]
        list[index] = list[maxIndex]
        list[maxIndex] = temp
        this.heapify(maxIndex)
      }
    }
    this.buildHeap = () => {
      for (let i = Math.floor(this.list.length / 2); i >= 0; i--) {
        this.heapify(i)
      }
      return this.list
    }
    this.extract = () => {
      const temp = this.list[0]
      this.list[0] = this.list[this.list.length - 1]
      this.list[this.list.length - 1] = temp
      const result = this.list.pop()
      this.heapify(0)
      return result
    }
    this.insert = (item) => {
      const { list } = this
      list.push(item)
      let index = list.length - 1
      let parentIndex = this.parent(index)
      while (list[parentIndex] !== undefined && this.compare(list[parentIndex], list[index]) > 0) {
        const temp = list[index]
        list[index] = list[parentIndex]
        list[parentIndex] = temp
        index = parentIndex
        parentIndex = this.parent(index)
      }
    }
    this.list = list
    this.compare = compare
    this.buildHeap()
  }
}

// Heap solution O(log(k) * n) similar to merge K sorted list
const nthSuperUglyNumber = (n, primes = []) => {
  const result = [1]
  const minHeap = new Heap(
    primes.map(prim => [prim, 0]),
    (
      [prim1, index1],
      [prim2, index2],
    ) => result[index1] * prim1
    - result[index2] * prim2,
  )
  while (result.length < n) {
    const [prim, index] = minHeap.extract()
    const num = prim * result[index]
    if (num > result[result.length - 1]) {
      result.push(num)
    }
    if (index + 1 <= result.length - 1) {
      minHeap.insert([prim, index + 1])
    }
  }
  return result[n - 1]
}