Introduction

In this blog post, we will explore how to solve the LeetCode problem "1175" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Return the number of permutations of 1 to n so that prime numbers are at prime indices (1-indexed.) (Recall that an integer is prime if and only if it is greater than 1, and cannot be written as a product of two positive integers both smaller than it.) Since the answer may be large, return the answer modulo 10^9 + 7. Example 1: Input: n = 5 Output: 12 Explanation: For example [1,2,5,4,3] is a valid permutation, but [5,2,3,4,1] is not because the prime number 5 is at index 1. Example 2: Input: n = 100 Output: 682289015 Constraints: 1 <= n <= 100

Explanation

Here's the solution:

• Count Primes: Determine the number of prime numbers within the range 1 to n. This dictates the number of fixed positions (prime indices) that must be occupied by prime numbers.
• Factorials: Calculate the factorial of the number of primes and the factorial of the number of non-primes (composite numbers and 1). These factorials represent the number of ways to arrange the primes in prime indices and the non-primes in non-prime indices, respectively.

• Modulo Arithmetic: Compute the product of these factorials modulo 10^9 + 7 to handle large numbers and satisfy the problem constraints.

• Runtime Complexity: O(n + sqrt(n)), Storage Complexity: O(1)

Code

    def numPrimeArrangements(n: int) -> int:
    """
    Calculates the number of permutations of 1 to n such that prime numbers
    are at prime indices (1-indexed).

    Args:
        n: The upper bound of the range of numbers (1 to n).

    Returns:
        The number of valid permutations modulo 10^9 + 7.
    """

    def is_prime(num):
        if num <= 1:
            return False
        for i in range(2, int(num**0.5) + 1):
            if num % i == 0:
                return False
        return True

    def factorial(num, mod):
        result = 1
        for i in range(1, num + 1):
            result = (result * i) % mod
        return result

    prime_count = 0
    for i in range(1, n + 1):
        if is_prime(i):
            prime_count += 1

    non_prime_count = n - prime_count
    mod = 10**9 + 7

    return (factorial(prime_count, mod) * factorial(non_prime_count, mod)) % mod