[B] [C] [D]

A super ugly number is a positive integer whose prime factors all appear in the primes array.

Given an integer n and an integer array primes, return the NTH super ugly number.

The problem data guarantees that the NTH super ugly number is in the range of 32-bit signed integers.

Example 1:

Input: n = 12, primes = [2,7,13,19] output: 32 description: given a primes array of length 4, primes = [2,7,13,19], the first 12 super-ugly sequences are: ,2,4,7,8,13,14,16,19,26,28,32 [1].Copy the code

Example 2:

Input: n = 1, primes = [2,3,5] output: 1 explanation: 1 has no prime factors, so all its prime factors are in the prime array primes = [2,3,5].Copy the code

Tip:

  • 1 <= n <= 106
  • 1 <= primes.length <= 100
  • 2 <= primes[i] <= 1000
  • Subject dataensure primes[i]It’s a prime number
  • primesAll values inEach other is not the sameAnd according to theIncreasing orderarrangement

Their thinking

Leetcode-264-ugly number II is the same as leetcode-264-ugly number II, except that the prime factors in leetcode-264-ugly number II are determined 2, 3, and 5, while the prime factors in leetcode-264-ugly number II are passed in through array parameters. Next, we take prime factors 2, 3 and 5 as examples to explain the process of finding the NTH ugly number.

To find the NTH ugly number, first of all, what is an ugly number? Definition of ugly numbers: positive integers containing only prime factors 2, 3 and/or 5.

Based on the above conditions, we multiply the ugliness numbers we have obtained by prime factors 2, 3 and 5, respectively, to obtain the subsequent ugliness numbers. Since 1 is the first ugliness number, this result can be obtained based on the above logic.

12 3 5 4 6 6 9 15 10 15 25 8 12 20... 2, 3, 5Copy the code

But there are two problems with the result sequence above:

  1. The sequence is not ordered
  2. Duplicate values exist

So how do you avoid these two problems when you’re trying to figure out all the ugly numbers?

  1. Initialize the result array and insert the first element1
  2. Defines a pointer to three prime factors, initialized to the subscript0
  3. Find the product of each prime factor and the value of its corresponding pointer in the result array
  4. Gets the minimum value in all products, which is the next ugly number
  5. Moves the pointer to the prime factor corresponding to the minimum one bit back
  6. Repeat the process until you get the number onenUgly Numbers

Through the above process, it is guaranteed that the ugly numbers are arranged in strict ascending order. When the product of multiple prime factors has the same minimum value, the pointer to each prime factor is moved back one bit, thus ensuring that there will be no duplicate results.

Understand the process of solving ugly numbers based on prime factors 2, 3, 5, only need to change the corresponding prime factors into primes array to complete the problem.

The demo

Code implementation

Var nthSuperUglyNumber = function(n, primes) {const arr = Array(n).fill(1), len = primes. Length, Inds = Array(len).fill(0), nums = [...primes]; For (let I = 1; i<n; I++){// get the minimum value of the product const min = math.min (... nums); Arr [I] = min; For (let j = 0; j<len; j++){ if(min === nums[j]){ inds[j]++; Nums [j] = arr[inds[j]]*primes[j]}} return arr[n-1]};Copy the code

At this point we have leetcode-313- super ugly number

If you have any questions or suggestions, please leave a comment!