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 Sam K., 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

More Math practice problems

See all Math problems →