{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "Write a program to find the `nth` super ugly number.\n",
    "\n",
    "Super ugly numbers are positive numbers whose all prime factors are in the\n",
    "given prime list `primes` of size `k`.\n",
    "\n",
    "**Example:**\n",
    "\n",
    "\n",
    "\n",
    "    Input: n = 12, primes = [2,7,13,19]\n",
    "    Output: 32\n",
    "    Explanation:[1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12\n",
    "                 super ugly numbers given primes = [2,7,13,19] of size 4.\n",
    "\n",
    "**Note:**\n",
    "\n",
    "  * `1` is a super ugly number for any given `primes`.\n",
    "  * The given numbers in `primes` are in ascending order.\n",
    "  * 0 < `k` ≤ 100, 0 < `n` ≤ 106, 0 < `primes[i]` < 1000.\n",
    "  * The nth super ugly number is guaranteed to fit in a 32-bit signed integer."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "nth_super_ugly_number (generic function with 1 method)"
     },
     "metadata": {},
     "execution_count": 1
    }
   ],
   "cell_type": "code",
   "source": [
    "# @lc code=start\n",
    "using LeetCode\n",
    "\n",
    "function nth_super_ugly_number(n::Int, primes::Vector{Int})\n",
    "    dp = fill(1, n)\n",
    "    len = length(primes)\n",
    "    cur_min = primes[:]\n",
    "    ptrs = fill(1, len)\n",
    "\n",
    "    @inbounds for i in 2:n\n",
    "        minn = minimum(cur_min)\n",
    "        dp[i] = minn\n",
    "        @simd for pidx in 1:len\n",
    "            if minn == cur_min[pidx]\n",
    "                ptrs[pidx] += 1\n",
    "                cur_min[pidx] = dp[ptrs[pidx]] * primes[pidx]\n",
    "            end\n",
    "        end\n",
    "    end\n",
    "    return dp[end]\n",
    "end\n",
    "# @lc code=end"
   ],
   "metadata": {},
   "execution_count": 1
  },
  {
   "cell_type": "markdown",
   "source": [
    "---\n",
    "\n",
    "*This notebook was generated using [Literate.jl](https://github.com/fredrikekre/Literate.jl).*"
   ],
   "metadata": {}
  }
 ],
 "nbformat_minor": 3,
 "metadata": {
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.10.1"
  },
  "kernelspec": {
   "name": "julia-1.10",
   "display_name": "Julia 1.10.1",
   "language": "julia"
  }
 },
 "nbformat": 4
}