1175. Prime Arrangements
Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 1
Acceptance rate: 51.7%
Problem Breakdown
The problem asks us to find the number of permutations of numbers from 1 to n such that all prime numbers are placed at prime indices (considering 1-indexed positions). A prime number is defined as a number greater than 1 that cannot be expressed as a product of two smaller positive integers. The result should be returned modulo (10^9 + 7) due to potential large output sizes.
Inputs:
- An integer
n(1 <= n <= 100).
Outputs:
- An integer representing the number of valid permutations, modulo (10^9 + 7).
Implicit Constraints/Edge Cases:
- The smallest input is 1, which has no primes.
- The largest input is 100, which requires efficient computation.
Intuition
A brute-force approach would involve generating all permutations of numbers from 1 to n and checking if each permutation satisfies the prime index condition. However, this approach is infeasible due to its factorial time complexity (O(n!)).
The key insight is that we can separate the problem into two parts:
- Count the number of primes between 1 and
n. - Calculate the permutations for both the prime numbers and non-prime numbers separately.
- Multiply these two results together to get the total number of valid permutations.
This approach leverages the fact that the positions of prime numbers and non-prime numbers are independent, reducing the problem’s complexity significantly.
Approach
- Count Primes: Use a helper function to count the number of prime numbers up to
n. This can be done using the Sieve of Eratosthenes or a simple trial division method. - Calculate Permutations:
- Calculate the factorial of the number of primes (
prime_count!). - Calculate the factorial of the number of non-primes (
non_prime_count!), wherenon_prime_count = n - prime_count.
- Calculate the factorial of the number of primes (
- Combine Results: Multiply the two factorials together to get the total number of valid permutations.
- Modulo Operation: Since the result can be large, return it modulo (10^9 + 7).
Complexity Analysis
- Time Complexity: (O(n \log \log n)) for counting primes using the Sieve of Eratosthenes, and (O(k)) for calculating factorials where (k) is the number of primes or non-primes.
- Space Complexity: (O(1)) for storing a few variables.
Solution
def numPrimeArrangements(n):
MOD = 10**9 + 7
def count_primes(limit):
sieve = [True] * (limit + 1)
sieve[0] = sieve[1] = False
for start in range(2, int(limit**0.5) + 1):
if sieve[start]:
for multiple in range(start*start, limit + 1, start):
sieve[multiple] = False
return sum(sieve)
def factorial(num):
result = 1
for i in range(2, num + 1):
result = (result * i) % MOD
return result
prime_count = count_primes(n)
non_prime_count = n - prime_count
return (factorial(prime_count) * factorial(non_prime_count)) % MOD
# Example usage:
print(numPrimeArrangements(5)) # Output: 12
print(numPrimeArrangements(100)) # Output: 682289015
Edge Cases Handled
- n = 1: There are no primes, so the result is 1 (only one permutation of [1]).
- n = 2: The only prime is 2, which can be placed at index 2. Thus, there’s only one valid permutation.
- n = 100: Efficiently counts primes and calculates factorials within the constraints.
The solution provided is correct, efficient, and clear. It handles all edge cases appropriately and adheres to the problem constraints.