What is the meaning of the passage?

Please help to design a program to find the NTH ugly number.

Ugly numbers are positive integers that are divisible by a or B or C.

The sample

Example 1:

Input: n = 3, a = 2, b = 3, c = 5 Output: 4 Explanation: ugly sequence is 2, 3, 4, 5, 6, 8, 9, 10... The third one is 4.Copy the code

Example 2:

Input: n = 4, a = 2, b = 3, c = 4 Output: 6 Explanation: ugly sequence is 2, 3, 4, 6, 8, 9, 12... The fourth of them is 6.Copy the code

Example 3:

Input: n = 5, a = 2, b = 11, c = 13 Output: 10 Explanation: Ugly sequence is 2, 4, 6, 8, 10, 11, 12, 13... The fifth of them is 10.Copy the code

Example 4:

Input: n = 1000000000, a = 2, B = 217983653, C = 336916467 Output: 1999999984Copy the code

Tip:

1 <= n, a, b, c <= 10^9 1 <= a * B * c <= 10^18 in this case the result is in the range of 1, 2 * 10^9Copy the code

Their thinking

Method 1 Cycle of violence (No doubt running out of time)Copy the code

answer

    var nthUglyNumber = function(n, a, b, c) {
    var num = 1;
    for (var i = 1; i <= n; num++) {
        if (num % a == 0 || num % b == 0 || num % c == 0) {
            i++;
        }
    }
    return num - 1;
};
Copy the code

Problem number two

1. To find out the possible range of this number, first of all, we can think and judge that the minimum value is N, and the maximum value is min(a,b, C) * n 2. Find the number of qualified values within the range of a value, that is, the sequence length nums. For example, in the following example where the final value is 6, the sequence is [2, 3, 4, 6] and the length is 4===n. But we're also going to get to 4 for 5, so we're going to keep finding the lowest value. Input: n = 4, a = 2, b = 3, c = 4 Output: 6 Explanation: ugly sequence is 2, 3, 4, 6, 8, 9, 12... The fourth of them is 6. 3. Compare the sequence length calculated by us with n in the question, if it is equal, it is the value. ===n =n =n =n =nCopy the code

Answer 2

Var maxComFn = function(a, b) {if (a % b === 0) {return b; } else { return maxComFn(b, a % b); Var minComFn = function(a, b) {var maxC = maxComFn(a, b) return a * b/maxC; } // The number of a, b, c - ab, ac, Var inNumsFn = function(a, b, c, c, c, c) num) { return Math.floor(num / a) + Math.floor(num / b) + Math.floor(num / c) - Math.floor(num / minComFn(a, b)) - Math.floor(num / minComFn(a, c)) - Math.floor(num / minComFn(c, b)) + Math.floor(num / minComFn(c, minComFn(a, b))); } var nthUglyNumber = function(n, a, b, c) { var maxCom = maxComFn(a, maxComFn(b, c)); let mid, left = n, right = n * Math.min(a, b, c); while (left < right) { mid = Math.floor((left + right) / 2); if (inNumsFn(a, b, c, mid) < n) { left = mid + 1; } else { right = mid; // All the way to the minimum. } } return right; };Copy the code

conclusion

Many problems seem to be complicated, but in fact they can be broken down to be done step by step, such as splitting problems, finding boundaries, and finally assembling and combining.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign