Skip to main content

1175. Prime Arrangements

easy

Count permutations of 1..n where every prime number sits at a prime-indexed position. A short combinatorics problem: count primes, then multiply factorials.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Return the number of permutations of 1 to n so that prime numbers are at prime indices (1-indexed). (Recall that an integer is prime if and only if it is greater than 1, and cannot be written as a product of two positive integers both smaller than it.) Since the answer may be large, return the answer modulo 10^9 + 7.

Constraints

  • 1 <= n <= 100

Examples

Example 1

Input
n = 5
Output
12

Explanation: For example [1,2,5,4,3] is a valid permutation, but [5,2,3,4,1] is not because the prime number 5 is at index 1.

Example 2

Input
n = 100
Output
682289015

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Let p = the count of primes in [1, n]. The answer is p! * (n - p)! — primes permute among prime positions, composites among the rest.

Hint 2

Count primes with the Sieve of Eratosthenes (or trial division — n is small here).

Hint 3

Multiply with modular arithmetic: keep every intermediate product mod 10^9 + 7.

Hint 4

Note that '1' is not prime and counts as a composite for placement.

Solution approach

Reveal approach

Step 1: count primes p in [1, n]. With n up to 100, trial division is fine — for each i from 2 to n check divisibility by every j from 2 to sqrt(i). Step 2: the answer is p! * (n - p)! mod (10^9 + 7) since primes can be placed in any of p! orderings on the p prime positions, and composites (including 1) in (n - p)! orderings on the remaining positions. Compute both factorials in a single pass, applying the mod after each multiplication. O(n * sqrt(n)) time for the prime count, O(n) for the factorials. O(1) space.

Complexity

Time
O(n * sqrt(n))
Space
O(1)

Related patterns

  • math
  • combinatorics
  • sieve-of-eratosthenes

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon

Practice these live with InterviewChamp.AI

Drill Prime Arrangements and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →