LeetCode 1175 - Prime Arrangements

The problem asks us to count how many permutations of numbers from 1 to n satisfy a specific condition: all prime numbers must appear at prime-numbered indices (1-indexed).

leetcodeeasymath

LeetCode Problem 1175

Difficulty: 🟢 Easy
Topics: Math

Solution

Problem Understanding

The problem asks us to count how many permutations of numbers from 1 to n satisfy a specific condition: all prime numbers must appear at prime-numbered indices (1-indexed). For instance, in the permutation [1,2,5,4,3] for n = 5, the primes 2, 3, and 5 appear at indices 2, 3, and 5 respectively, all of which are prime positions, so this permutation is valid. In contrast, [5,2,3,4,1] is invalid because 5 is at index 1, which is not prime.

The input n is an integer between 1 and 100. The output is a single integer, the number of valid permutations modulo 10^9 + 7.

The constraints indicate that the solution must handle relatively small n, but the total number of permutations grows factorially (n!), so naive generation of all permutations is computationally infeasible. Important edge cases include small values of n (like 1 or 2), where primes may be few or none, and values where all numbers are prime or non-prime.

Approaches

A brute-force approach would generate all permutations of numbers from 1 to n and check for each permutation if all primes are at prime indices. While this guarantees correctness, it has a factorial time complexity (O(n!)), which is infeasible for n up to 100.

The key insight for an optimal solution is combinatorial. We do not need to generate all permutations. Instead, we can separate numbers into primes and non-primes. Let p be the number of primes in 1..n. There are exactly p prime positions and n-p non-prime positions. To count valid permutations:

  1. We can arrange the p primes in the p prime positions in p! ways.
  2. We can arrange the n-p non-primes in the n-p non-prime positions in (n-p)! ways.
  3. Multiply these two factorials to get the total number of valid permutations.

Finally, return the result modulo 10^9 + 7.

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n) Generate all permutations and filter valid ones
Optimal O(n * sqrt(n)) O(n) Count primes using a sieve, then compute factorials modulo 10^9+7

Algorithm Walkthrough

  1. Count primes: Use a simple sieve or primality check up to n to count how many numbers in 1..n are prime. This determines how many prime positions we need to fill.
  2. Compute factorials modulo 10^9+7: Compute the factorial of p (primes) and n-p (non-primes) modulo 10^9+7. This prevents integer overflow.
  3. Multiply factorials: Multiply p! and (n-p)! modulo 10^9+7. The result is the number of valid permutations.
  4. Return result: Output the computed value.

Why it works: The invariant is that prime numbers must occupy prime indices, and non-prime numbers occupy non-prime indices. By counting primes and non-primes separately and arranging them independently in their respective positions, we ensure all permutations counted are valid.

Python Solution

class Solution:
    def numPrimeArrangements(self, n: int) -> int:
        MOD = 10**9 + 7

        # Helper function to count primes using simple primality check
        def count_primes(x: int) -> int:
            if x < 2:
                return 0
            primes = [True] * (x + 1)
            primes[0] = primes[1] = False
            for i in range(2, int(x**0.5) + 1):
                if primes[i]:
                    for j in range(i*i, x + 1, i):
                        primes[j] = False
            return sum(primes)

        prime_count = count_primes(n)
        non_prime_count = n - prime_count

        # Helper function to compute factorial modulo MOD
        def factorial(k: int) -> int:
            result = 1
            for i in range(2, k + 1):
                result = (result * i) % MOD
            return result

        return (factorial(prime_count) * factorial(non_prime_count)) % MOD

The implementation first counts primes up to n using a sieve. Then it computes factorials of the number of primes and non-primes modulo 10^9 + 7. Multiplying these factorials gives the number of valid permutations. Each function is isolated for clarity and correctness.

Go Solution

func numPrimeArrangements(n int) int {
    const MOD = 1_000_000_007

    // Count primes using sieve
    primes := make([]bool, n+1)
    for i := 2; i <= n; i++ {
        primes[i] = true
    }
    for i := 2; i*i <= n; i++ {
        if primes[i] {
            for j := i * i; j <= n; j += i {
                primes[j] = false
            }
        }
    }

    primeCount := 0
    for i := 2; i <= n; i++ {
        if primes[i] {
            primeCount++
        }
    }
    nonPrimeCount := n - primeCount

    // Factorial modulo MOD
    factorial := func(k int) int {
        res := 1
        for i := 2; i <= k; i++ {
            res = (res * i) % MOD
        }
        return res
    }

    return (factorial(primeCount) * factorial(nonPrimeCount)) % MOD
}

The Go version follows the same logic as Python. The primary differences are Go-specific: we explicitly create a boolean slice for the sieve, and integer arithmetic requires modulo at each multiplication to prevent overflow.

Worked Examples

Example 1: n = 5

Count primes: [2,3,5] → 3 primes

Prime positions: indices [2,3,5] → 3 positions

Non-primes: [1,4] → 2 positions

Factorials: 3! = 6, 2! = 2

Multiply: 6 * 2 = 12 → valid permutations.

Example 2: n = 100

Count primes up to 100 → 25 primes, 75 non-primes

Factorials modulo 10^9 + 7:

25! * 75! % (10^9 + 7) = 682289015

Complexity Analysis

Measure Complexity Explanation
Time O(n * sqrt(n)) Counting primes using a sieve takes O(n log log n) ≈ O(n * sqrt(n)) and factorial computation is O(n)
Space O(n) Sieve array of size n+1 and constant extra variables

The factorial computation is linear and the sieve dominates space complexity.

Test Cases

# test cases
assert Solution().numPrimeArrangements(1) == 1  # only 1 number, valid
assert Solution().numPrimeArrangements(2) == 1  # primes=[2], prime positions=[2], only 1 valid permutation
assert Solution().numPrimeArrangements(5) == 12  # example 1
assert Solution().numPrimeArrangements(100) == 682289015  # example 2
assert Solution().numPrimeArrangements(10) == 17280  # small n with multiple primes
Test Why
n = 1 Minimal input
n = 2 Single prime, small size
n = 5 Example from problem
n = 100 Maximum constraint
n = 10 Small size, multiple primes

Edge Cases

  1. n = 1: There are no prime numbers, so the only permutation [1] is trivially valid. Implementation correctly handles zero primes with factorial(0) = 1.
  2. n = 2: Only one prime (2) exists, and only one prime position (index 2). This ensures factorial calculations handle prime and non-prime counts of 1 and 1 correctly.
  3. n = 100: The largest allowed input stresses the factorial and modulo arithmetic. Without modulo at each multiplication, integer overflow would occur. The algorithm correctly applies modulo to prevent overflow.

This solution generalizes for any n ≤ 100 while handling edge cases like minimal input, only one prime, or large input with many primes.