Prime Arrangements Solution in Python

Explore More Solutions

Problem Description

Ah, the classic “Prime Arrangements” problem! It’s like trying to organize a party where only the cool kids (the prime numbers) get to sit at the VIP table. The rest? Well, they can just hang out in the back. The task is simple: given a number n, you need to find out how many ways you can arrange the prime numbers from 1 to n while keeping the non-prime numbers in their own little corner.

Imagine you’re at a high school reunion, and you have to arrange the seating. You want all the popular kids (primes) to sit together, while the rest (non-primes) can just figure it out. The catch? You can’t just throw them together randomly; you need to calculate the arrangements mathematically.

Code Solution


class Solution:
    def numPrimeArrangements(self, n: int) -> int:
        kMod = 1_000_000_007

        def factorial(n: int) -> int:
            fact = 1
            for i in range(2, n + 1):
                fact = fact * i % kMod
            return fact

        count = self._countPrimes(n)
        return factorial(count) * factorial(n - count) % kMod

    def _countPrimes(self, n: int) -> int:
        isPrime = [False] * 2 + [True] * (n - 1)
        for i in range(2, int(n**0.5) + 1):
            if isPrime[i]:
                for j in range(i * i, n + 1, i):
                    isPrime[j] = False
        return sum(isPrime)

Approach Explanation

The code begins by defining a function to calculate the factorial of a number, which is essential for determining the number of arrangements. It then counts the prime numbers up to n using the Sieve of Eratosthenes method, which is a fancy way of saying it marks non-prime numbers efficiently. Finally, it calculates the number of arrangements by multiplying the factorial of the count of primes and the factorial of the non-prime count, all while keeping the results within a modulo to avoid overflow.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n log log n)
Space Complexity	O(n)

Real-World Example

Think of a group of friends planning a movie night. They want to sit in a way that the movie buffs (primes) are together, while the casual viewers (non-primes) are seated elsewhere. If there are 10 friends, and 4 of them are movie buffs, the number of ways they can arrange themselves is calculated using the same logic as the Prime Arrangements problem.