Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

What is the exclusion principle

The inclusion and exclusion principle is used to find the union of sets.

See such a question, a summer training class, each student will attend, the soccer team to participate in the 25 people, to participate in the volleyball has 22, 24 people attended the swimming team, football and volleyball all attend have 12 people, football, swimming for nine people, volleyball, swimming to eight people, three to three people, ask how many students are there in the class?

The problem is abstracted as: elements are divided into three types, A,B and C, and there are repetitions between the types, which can be expressed by Venn diagram as follows:

When we find the union of A, B, and C, if we use A+B+C, some elements will be repeated, we can calculate A+B+C – (A∩B+B∩C+A∩ B∩C) +A∩ B∩C.

To expand to multiple sets, we first calculate the size of all the individual sets, then subtract the intersecting parts of all two sets, add back the intersecting parts of all three sets, subtract the intersecting parts of all four sets, and so on, until we get to the intersecting parts of all sets. That’s the basic definition of the exclusion principle.

We can simply call it “odd plus even minus,” which means that the odd numbers are added to the answer, and the even numbers are subtracted.

Going back to the original question, you could write down the answer (25+22+24) – (12+9+8) + 3 = 45.

LeetCode of actual combat

1201. The number of ugly III

Given four integers: n, a, b, c, please design an algorithm to find the NTH ugly number.

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

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

Although the subject is medium, the actual difficulty is greater than many difficulties, involving more knowledge points.

First of all, combined with the above introduction, we can get the number of ugly numbers within any x, namely:

The number of times that a is divisible, plus the number of times that B is divisible, plus the number of times that C is divisible, minus the number of times that a and B are divisible, plus the number of times that a, B, and C are divisible.

So to figure out how many times a and B can be divisible at the same time, we need to figure out the least common multiple of a and b, LCM, and then we need to figure out how many times x over LCM, which is the number of times within x that a and B can be divisible at the same time.

And to ask for the least common multiple, we need to find the greatest common divisor first, we can find the greatest common divisor through the toss and turn division, and then divide the greatest common divisor by the product of two numbers is the least common multiple. The specific code is as follows:

/** * find the greatest common divisor of a and b *@param {number} a
 * @param {number} b
 * @return {number}* /
function gcd(a, b) {
    return b == 0 ? a : gcd(b, a % b)
}
/** * find the least common multiple of a and b *@param {number} a
 * @param {number} b
 * @return {number}* /
function lcm(a, b) {
    return a * b / gcd(a, b)
}
Copy the code

And then, if we can figure out the number of ugly numbers within x, then we can figure out whether the number of ugly numbers in the interval is greater than or equal to n by dichotomy, enumerating the answers. Complete code:

function gcd(a, b) {
    return b == 0 ? a : gcd(b, a % b)
}
function lcm(a, b) {
    return a * b / gcd(a, b)
}
/ * * *@param {number} n
 * @param {number} a
 * @param {number} b
 * @param {number} c
 * @return {number}* /
var nthUglyNumber = function(n, a, b, c) {
    // find the ugly number within x
    function calc(x) {
        // Contains the number of sets
        let v1 = Math.floor(x / a) + Math.floor(x / b) + Math.floor(x / c);
        // Two sets
        let v2 = Math.floor(x / lcm(a, b))
            + Math.floor(x / lcm(b, c))
            + Math.floor(x / lcm(a, c));
        // Set with three sets
        let v3 = x / lcm(lcm(a, b), c);

        return v1 - v2 + v3;
    }
    // Binary solution
    let l = n, r = 2000000000, ans = l;
    while (l <= r) {
        let m = Math.floor((l + r) / 2);
        if (calc(m) >= n) {
            ans = m;
            r = m - 1;
        } else {
            l = m + 1; }}return ans;
};
Copy the code

The resources

  • Principle of Inclusion and Exclusion (translation)
  • Baidu Encyclopedia – Exclusion principle