Look a hundred times beauty, beauty is not necessarily yours. But if you run the algorithm a hundred times, the knowledge is yours

Who can have nine floors? No need to get up!

Title address

The title

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:

Input: k = 5 Output: 9Copy the code

Their thinking

  • We use arrays to record these prime factors
  • The generation rule of number is3, 5, 7Respectively on3, 5, 7A multiple of
  • When I multiply it by something like15This is a3again5When a multiple of, the number of repeats is generated15 * 3and9 * 5
  • So we need to get rid of duplicates
  • We use three Pointers to record each3A multiple of,5Multiples and7A multiple of
  • Only smaller values are recorded by comparing the corresponding multiples, and the pointer is moved back one bit, repeating k times

The problem solving code

var getKthMagicNumber = function(k) {
    if(k==1) return k
    let arr = [1]
    let i3 = 0
    let i5 = 0
    let i7 = 0
    for(let i=1; i<k; i++){ arr[i] =Math.min(arr[i3]*3,arr[i5]*5,arr[i7]*7)
        if(arr[i]==arr[i3]*3) i3++;
        if(arr[i]==arr[i5]*5) i5++;
        if(arr[i]==arr[i7]*7) i7++;
    }
    return arr[k-1]};Copy the code

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