“This is the 25th day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

[B] [C] [D]

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:

Input: k = 5 Output: 9Copy the code

So the first question we’re going to solve is how do we get more numbers with prime factors of 3, 5, and 7

You can start with 1, multiply 1 by 3,5,7 to get 3,5,7, and then repeat the process for the following numbers, and you get more numbers with only 3, 5, and 7 prime factors

Doing this to 7 gives you the following array

,3,5,7,9,15,21,15,25,35,21,35 [1]

It can be seen that in this case, although we get the numbers that meet the requirements of the question, there will be repeated cases and situations in which the front is large and the back is small

Answer key 1

Based on the above conditions, it is natural for us to think of the first way to solve the problem:

  1. Multiply each value by 3, 5, and 7 to get more numbers
  2. Insert these arrays in turn into an array
  3. Check whether the value exists in the array before inserting it. If so, skip it
  4. When you insert an array, instead of putting it at the end of the array, you find a place where everything in front is less than or equal to it, and everything in the back is greater than it
  5. That’s how we find the right oneskThe number, the firstkOne is the result of this problem

The code is as follows:

Var getKthMagicNumber = function(k) {var getKthMagicNumber = function(k) { // If the number of values in the array is less than k*1.3, the number of values in the array is less than k*1.3. While (arr.length< math.floor (k*1.3)){const num1 = arr[cur]*3, num2 = arr[cur]*5, num3 = arr[cur]*7; if(arr.indexOf(num1)===-1) arr = insert(arr,num1); if(arr.indexOf(num2)===-1) arr = insert(arr,num2); if(arr.indexOf(num3)===-1) arr = insert(arr,num3); cur++; Function insert(arr,num){let cur = arr. Length -1; while(arr[cur]>num){ cur--; } arr. Splice (cur + 1, 0, num); return arr; }}Copy the code

It should be noted that the KTH value to be found is not the KTH value in the above process, but after the KTH value. Here, I have not carefully calculated how much more is needed to produce the correct KTH value, but roughly increased the number by 30%

Answer key 2

In the process of solving the above problems, it is necessary to determine whether the current value has appeared, and the new value needs to be inserted into the appropriate position during the insertion process, so is there any way to directly obtain the correct value of the current position?

Here we can use the following method

Define three Pointers representing the current 3, 5, and 7 values to be multiplied at the subscript position in the array. Initialize three Pointers to 0, the position in the array with the value 1

The smallest of the three numbers is then determined to be the value of the current position by multiplying 3, 5, and 7 by the corresponding value of the pointer

The pointer to the selected value is then moved back one bit

This ensures that each value is the smallest of all subsequent values, updating it to the current position, which is the correct value for the current position

The code is as follows:

Var getKthMagicNumber = function(k) {// initialize array const arr = [1]; // let tail3 = tail5 = tail7 = 0; for(let i = 1; i<k; // Get the product of each prime factor and its pointer const num1 = arr[tail3]*3, num2 = ARr [tail5]*5, num3 = arr[tail7]*7; Arr [I] = math. min(num1,num2,num3); / / will correspond to the position of the pointer move back one if (arr [I] = = = num1) tail3 + + the if (arr [I] = = = num2) tail5 + + the if (arr [I] = = = num3) tail7 + +} return arr [k - 1]};Copy the code

It is important to note that we cannot use else if when we move the pointer, because there will be duplicate values

Here we have leetcode- Interview question 17.09- the KTH number

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