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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Prime Arrangements

Number: 1279

Difficulty: Easy

Paid? No

Companies: Amazon

Problem Description

Given an integer n, count the number of valid permutations of numbers from 1 to n such that every prime number in the permutation occupies an index that is also a prime number (using 1-indexing). The result should be returned modulo 10^9 + 7.

Key Insights

  • Only the positions that are prime numbers matter; prime numbers must be placed at these prime indices.
  • First, count the number of prime numbers between 1 and n (denote it as prime_count). The non-prime count is then (n - prime_count).
  • The valid arrangements are the product of factorial(prime_count) and factorial(n - prime_count) because:
    • The prime_count primes can be arranged among prime indices in factorial(prime_count) ways.
    • The remaining (n - prime_count) non-primes can be arranged in the remaining positions in factorial(n - prime_count) ways.
  • Use modulo arithmetic at every multiplication step to handle large numbers.

Space and Time Complexity

Time Complexity: O(n * sqrt(n)) or O(n log log n) if optimized with a Sieve of Eratosthenes (n is at most 100). Space Complexity: O(n) for storing prime flags if using the sieve.

Solution

We first compute how many numbers in the range [1, n] are prime. For n up to 100, a simple check or a small sieve is efficient enough. Once the number of primes (prime_count) is determined, the valid arrangement count is simply factorial(prime_count) multiplied by factorial(n - prime_count) taken modulo 10^9 + 7.

We maintain a loop to compute factorial values while taking modulus. The problem is then reduced to arithmetic and simple combinatorial factorial computation.

Code Solutions

# Python solution for Prime Arrangements

MOD = 10**9 + 7

def count_primes(n):
    # Function to count number of primes in [1, n]
    if n < 2:
        return 0
    # Initialize sieve list
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False  # 0 and 1 are not prime
    for num in range(2, int(n**0.5) + 1):
        if is_prime[num]:
            for multiple in range(num*num, n+1, num):
                is_prime[multiple] = False
    # Sum up the prime numbers
    return sum(is_prime)

def prime_arrangements(n):
    # Count how many numbers in range [1, n] are prime
    prime_count = count_primes(n)
    # Calculate factorial for primes and non-primes with modulo
    result = 1
    # Factorial for prime_count numbers
    for i in range(1, prime_count + 1):
        result = (result * i) % MOD
    # Factorial for non-prime count = n - prime_count
    for i in range(1, n - prime_count + 1):
        result = (result * i) % MOD
    return result

# Example usage:
n = 5
print(prime_arrangements(n))  # Expected Output: 12
← Back to All Questions