algoadvance

Given an integer n (1 <= n <= 100), you need to return the number of prime arrangements. The number prime arrangements is the number of permutations of the first n positive integers such that prime numbers are at prime indices (1-indexed).

Return the number of prime arrangements modulo 10^9 + 7.

Clarifying Questions

1. Should I consider 1 as a prime number?
   • No, 1 is not a prime number. Prime numbers are greater than 1 and are only divisible by 1 and themselves.
2. If n is 1, what should the function return?
   • Since 1 is not a prime, there is only one arrangement: [1].

Strategy

1. Determine Prime Numbers: Calculate how many of the numbers from 1 to n are prime.
2. Calculate Permutations: Given num_primes prime numbers and (n - num_primes) non-prime numbers:
   • Calculate the factorial of num_primes since those can be arranged amongst themselves.
   • Calculate the factorial of (n - num_primes) for the non-prime numbers.
3. Combine Results: Multiply the two factorial results and take the result modulo 10^9 + 7.

Code

from math import factorial

MOD = 10**9 + 7

def numPrimeArrangements(n: int) -> int:
    def is_prime(num):
        if num <= 1:
            return False
        if num <= 3:
            return True
        if num % 2 == 0 or num % 3 == 0:
            return False
        i = 5
        while i * i <= num:
            if num % i == 0 or num % (i + 2) == 0:
                return False
            i += 6
        return True

    num_primes = sum(1 for i in range(1, n + 1) if is_prime(i))
    non_primes = n - num_primes

    return (factorial(num_primes) * factorial(non_primes)) % MOD

# Example usage:
print(numPrimeArrangements(5))  # output should be 12

Time Complexity

• Prime Check Time Complexity: O(n * sqrt(n)) because for each i in the range from 1 to n, we are potentially performing a check for primes that takes O(sqrt(n)).
• Factorial Computation Time Complexity: O(n) for both the primes and non-primes factorials.

Given the constraints, this approach will be efficient.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?