1175. prime number arrangement: application of multiplication principle

Title Description

This is a LeetCode Upper 1175. Permutation of prime numbers , The difficulty is Simple .

Tag : 「 mathematics 」、「 Combinatorial number 」、「 Two points 」、「 The meter 」

Please help me to To   Number design arrangement scheme , Make all of 「 Prime number 」 Should be placed in 「 Prime index 」（ Index from Start ） On ; You need to return the total number of possible solutions .

Let's review 「 Prime number 」： The prime number must be greater than Of , And it cannot be expressed by the product of two positive integers less than it .

Because the answer could be big , So please return to the answer model mod   Then the result is .

Example 1：

 Input ：n = 5

 Output ：12
 explain ： for instance ,[1,2,5,4,3]  Is an effective arrangement , but  [5,2,3,4,1]  No , Because in the second case, prime numbers  5  It is wrongly placed in the index as  1  Location .

Example 2：

 Input ：n = 100

 Output ：682289015

Tips ：

The meter + Two points + mathematics

According to the meaning , The problem can be transformed into a solution The number of prime numbers within , Write it down as , At the same time, the number of non prime numbers is .

The number of placement schemes for prime numbers is , The number of placement schemes for non prime numbers is , according to 「 Multiplication principle 」 The total number of placement schemes is .

We can go through 「 The meter 」 The way to Primes within are preprocessed to arrays list in , For each for , We find the first satisfaction 「 Value less than or equal to 」 The location of , So we know The number of prime numbers within the range .

Code ：

class Solution {
    static int MOD = (int)1e9+7;
    static List<Integer> list = new ArrayList<>();
    static {
        for (int i = 2; i <= 100; i++) {
            boolean ok = true;
            for (int j = 2; j * j <= i; j++) {
                if (i % j == 0) ok = false;
            }
            if (ok) list.add(i);
        }
    }
    public int numPrimeArrangements(int n) {
        int l = 0, r = list.size() - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (list.get(mid) <= n) l = mid;
            else r = mid - 1;
        }
        int a = r + 1, b = n - a;
        long ans = 1;
        for (int i = b; i > 1; i--) ans = ans * i % MOD ;
        for (int i = a; i > 1; i--) ans = ans * i % MOD ;
        return (int)ans;
    }
}

• Time complexity ： The complexity of dichotomy is , The complexity of calculating the number of schemes is . The overall complexity is
• Spatial complexity ： , among by The number of prime numbers within

The meter + mathematics

Further more , For specific for , We're preprocessing Prime number hours within , It has been determined that How many prime numbers are there in , Thus, the binary operation is omitted .

Using arrays cnts Record the number of prime numbers within the current value range , Meaning in The number of prime numbers in the range is .

Code ：

class Solution {
    static int MOD = (int)1e9+7;
    static int[] cnts = new int[110];
    static {
        List<Integer> list = new ArrayList<>();
        for (int i = 2; i <= 100; i++) {
            boolean ok = true;
            for (int j = 2; j * j <= i; j++) {
                if (i % j == 0) ok = false;
            }
            if (ok) list.add(i);
            cnts[i] = list.size();
        }
    }
    public int numPrimeArrangements(int n) {
        int a = cnts[n], b = n - a;
        long ans = 1;
        for (int i = b; i > 1; i--) ans = ans * i % MOD ;
        for (int i = a; i > 1; i--) ans = ans * i % MOD ;
        return (int)ans;
    }
}

• Time complexity ：
• Spatial complexity ： , among

Last

This is us. 「 Brush through LeetCode」 The first of the series No.1175 piece , The series begins with 2021/01/01, As of the start date LeetCode I have in common 1916 questions , Part of it is a locked question , We will finish all the questions without lock first .

In this series , In addition to explaining the idea of solving problems , And give the most concise code possible . If the general solution is involved, there will be corresponding code templates .

In order to facilitate the students to debug and submit code on the computer , I've built a warehouse ：https://github.com/SharingSource/LogicStack-LeetCode .

In the warehouse address , You can see the links to the series 、 The corresponding code of the series 、LeetCode Links to the original problem and other preferred solutions .

More, more, more popular 「 written examination / interview 」 Relevant information can be found in the beautifully arranged Gather new bases