Leetcode PHP solution -- d124 1175 Prime Arrangements

D124 1175. Prime Arrangements

Title Link

1175. Prime Arrangements

Topic analysis

This question, give a number n to generate an array from 1 to N. how many permutations make the number of prime digits prime? Where 1 < = n < = 100

Since the final return value may be large, please return the result after mod (10 * * 9 + 7).

thinking

In other words, the numbers in the prime digits can be arranged arbitrarily, and the remaining non prime digits can be arranged arbitrarily. Therefore, we can calculate the two cases separately and multiply them.

Since the prime number of n can be changed to the time range of 100.

Second, we need to know how many prime numbers there are before a given number n. This is relatively simple. We only need to use array for the keys and values of the prime array we generated earlier_ Flip function can be reversed. After that, the permutation number can be calculated by factorial.

For non prime numbers, we use the range function to generate values from 1 to 100, and then use array_ The diff function generates a non prime array. Value minus key is the number of non prime numbers.

So let's use is first_ Set determines whether the given n is in a prime array or a non prime array. In the case of prime arrays, just take n as the key and get the value from the array. In the case of non prime array, get the value + 1 by using n as the key from the non prime array to get n and how many non prime numbers there are before. Why + 1 is because of array_diff returns a subscript starting from 0. N minus the number of non prime numbers equals the number of prime numbers.

Well, now that we have prime numbers and non prime numbers, what we need to do is factorial. We all know that the value after factorization rises very fast, so I take a module for each number multiplied.

First use the range function to generate numbers that need to participate in factorial, and then use array_values get these numbers, and finally use array_reduce transforms a one-dimensional array into a number. Here, prime numbers are the same as non prime numbers, so I won't explain more.

It should be noted that the return of n includes 1, that is, the number of prime numbers will be 0. At this time, array is performed_ Reduce will return 0. If you multiply it again, it will return 0. Therefore, I also set the minimum value of 1 with the max function after calculation.

Final code

<?php
class Solution {

    /**
     * @param Integer $n
     * @return Integer
     */
    function numPrimeArrangements($n) {
        $primes = [1 =>2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97];
        $nonPrimes = array_values(array_diff(range(1,100), $primes));
        $primesBeforeIndex = array_flip($primes);
        $nonPrimesBeforeIndex = array_flip($nonPrimes);
        if(isset($primesBeforeIndex[$n])){
            $primeAmount = $primesBeforeIndex[$n];
            $nonePrimeAmount = $n - $primeAmount;
        }
        else{
            $nonePrimeAmount = $nonPrimesBeforeIndex[$n]+1;
            $primeAmount = $n - $nonePrimeAmount;
        }
        $primesPermutation = array_reduce(array_values(range(1,$primeAmount)), function($carry, $item){
            $carry *= $item;
            return $carry%(pow(10,9)+7);
        },1);
        $primesPermutation = max(1, $primesPermutation);
        $nonPrimePermutation = array_reduce(array_values(range(1,$nonePrimeAmount)), function($carry, $item){
            $carry *= $item;
            return $carry%(pow(10,9)+7);
        },1);
        $nonPrimePermutation = max(1, $nonPrimePermutation);
        return ($primesPermutation * $nonPrimePermutation)%(pow(10,9)+7);
    }
}

If you think this article is useful to you, you are welcome to use it Love power generation support.

Tags: PHP leetcode

Posted by raquelzinha on Fri, 13 May 2022 17:15:13 +0300