We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Prime Arrangements

Difficulty: Easy

Problem Description

Return the number of permutations of 1 to n so that prime numbers are at prime indices (1-indexed). Since the answer may be large, return the answer modulo 10^9 + 7.

Key Insights

  • Identify prime numbers up to n using the Sieve of Eratosthenes.
  • Determine the count of prime numbers and non-prime numbers in the range from 1 to n.
  • Calculate the number of valid permutations by:
    • Finding permutations of prime numbers at prime indices.
    • Finding permutations of non-prime numbers at non-prime indices.
  • Use factorial calculations to determine the number of arrangements.

Space and Time Complexity

Time Complexity: O(n log log n) for the Sieve of Eratosthenes and O(n) for factorial calculations, resulting in an overall complexity of O(n log log n). Space Complexity: O(n) for storing prime flags.

Solution

To solve the problem, we can break it down into the following steps:

  1. Use the Sieve of Eratosthenes to find all prime numbers up to n.
  2. Count the total number of prime indices and the total number of prime numbers.
  3. Calculate the factorial of the count of prime numbers and the count of non-prime numbers.
  4. Multiply these two results together and take the modulo 10^9 + 7 to get the final answer.

Code Solutions

def numPrimeArrangements(n):
    MOD = 10**9 + 7
    
    # Helper function to determine if a number is prime
    def sieve_of_eratosthenes(limit):
        is_prime = [True] * (limit + 1)
        is_prime[0], is_prime[1] = False, False
        
        for i in range(2, int(limit**0.5) + 1):
            if is_prime[i]:
                for j in range(i * i, limit + 1, i):
                    is_prime[j] = False
        return is_prime

    # Get prime number indicators
    is_prime = sieve_of_eratosthenes(n)
    
    # Count primes
    prime_count = sum(is_prime[1:n + 1])
    non_prime_count = n - prime_count
    
    # Calculate factorial mod
    def factorial(num):
        result = 1
        for i in range(2, num + 1):
            result = (result * i) % MOD
        return result
    
    return (factorial(prime_count) * factorial(non_prime_count)) % MOD
← Back to All Questions