Leetcode 1175. Prime Arrangements

Problem statement

https://leetcode.com/problems/prime-arrangements/

Solution

What we need to do is calculate number of prime numbers x and then return x! * (n-x)!.

Complexity

We can say it is O(n*sqrt(n)) for this solution, if we do not count the fact that factorials can be big. However it is easy to make it true O(n*sqrt(n)). Also we can make it O(n log log n) or even O(n) if we use Sieve.

Code

class Solution:
    def numPrimeArrangements(self, n):
        def isPrime(x):
            for i in range(2, int(sqrt(x)) + 1):
                if x % i == 0: return False
            return True
        x = sum(isPrime(i) for i in range(2, n + 1))
        return (factorial(x) * factorial(n - x)) % (10**9 + 7)