Prime Arrangements Solution in Java

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 problem is simple yet perplexing: given a number n, you need to find out how many ways you can arrange n people such that all the prime-numbered guests are in prime-numbered positions.

Imagine you have a group of friends, and you want to arrange them in a line for a photo. But wait! Only the friends whose ages are prime numbers can stand in the prime-numbered spots. So, if you have 10 friends, and only 4 of them are prime (2, 3, 5, 7), you need to figure out how many different ways you can arrange them. Sounds like a fun party, right?

Code Solution


class Solution {
  public int numPrimeArrangements(int n) {
    final int count = countPrimes(n);
    return (int) (factorial(count) * factorial(n - count) % kMod);
  }

  private static final int kMod = 1_000_000_007;

  private int countPrimes(int n) {
    boolean[] prime = new boolean[n + 1];
    Arrays.fill(prime, 2, n + 1, true);

    for (int i = 2; i * i <= n; ++i)
      if (prime[i])
        for (int j = i * i; j <= n; j += i)
          prime[j] = false;

    int count = 0;

    for (boolean p : prime)
      if (p)
        ++count;

    return count;
  }

  private long factorial(int n) {
    long res = 1;
    for (int i = 2; i <= n; ++i)
      res = res * i % kMod;
    return res;
  }
}

Approach Explanation

The code works by first counting how many prime numbers exist up to n. It uses the Sieve of Eratosthenes algorithm to efficiently find all prime numbers. Once we have the count of prime numbers, we calculate the factorial of that count and the factorial of the non-prime count (which is simply n - count). The final answer is the product of these two factorials, taken modulo 1,000,000,007 to keep the numbers manageable.

Time and Space Complexity

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

Real-World Example

Let’s say you’re organizing a talent show with 10 contestants. Only the ones who can juggle (the prime numbers) get to perform in the prime-numbered slots. You have 4 jugglers (2, 3, 5, 7) and 6 non-jugglers. The number of ways to arrange them is the answer to your problem!