Subject to introduce

Some numbers have only 3, 5, and 7 prime factors. design an algorithm to find the KTH number. Note that it is not necessary to have these prime factors, but to contain no other prime factors. For example, the first numbers would be 1,3,5,7,9,15,21 in that order.

Example 1

Enter k =5Output:9
Copy the code

Interview question 17.09. Number K, station B

Their thinking

If we assume that all of these numbers are stored in an array, then any numbers that are not in the array are numbers whose prime factors are not 3, 5, and 7

The numbers in this array can be represented as 3a * 5b * 7C, and a, B, and C must be in the array or 0 or 1 (a, b, and C are not all 0, and 1 contains no prime factors).

If you multiply 3, 5, and 7 by the numbers in the array, you will get numbers that have only 3, 5, and 7 prime factors

2. Define p3, p5, p7 as the first position 3 in the array. Calculate the value of 3 * p3, 5 * p5 and 7 * p7 respectively, and then compare the size of these three values 4. Place the minimum value in the next digit of the array 5. Move the pointer whose result equals the minimum value to the next digit of the current position 6. Repeat the process 3-5 until the KTH number is obtained

The problem solving code

var getKthMagicNumber = function(k) {
    let p3 = 0, p5 = 0, p7 = 0
    const arr = [1]
    while (--k) {
        const val_3 = arr[p3] * 3, val_5 = arr[p5] * 5, val_7 = arr[p7] * 7
        const val = Math.min(val_3, Math.min(val_5, val_7))
        arr.push(val)
        val_3 === val && p3++
        val_5 === val && p5++
        val_7 === val && p7++
    }
    return arr[arr.length - 1]};Copy the code

So that’s the answer to this question, Welcome to see my other article [luffy]_ ring list [Luffy]_ happy number [Luffy]_ reverse list [Luffy]_ reverse list [Luffy]_K group of flipped list [Luffy]_ rotation list [Luffy]_ pairwise swap list of nodes [Luffy]_ recent requests