Skip to main content
Talentd

Prime Arrangements - Solution & Explanation

EasyMath13 min readAsked at: Amazon
Practice this problem

Problem Statement

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.

 

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

 

Constraints:

  • 1 <= n <= 100

Approach Overview

Problem Overview: You are given an integer n. Arrange numbers from 1 to n so that prime numbers appear only at prime indices (1-indexed). The task is to count how many valid permutations exist, returning the result modulo 1e9 + 7.

The key observation: only the count of primes matters, not their specific values. If there are p primes ≤ n, then exactly p positions in the permutation are prime indices. Those slots must be filled with the p prime numbers in any order. The remaining n - p non-prime numbers fill the remaining positions.

Approach 1: Prime Counting with Factorials (O(n log log n) time, O(n) space)

First compute how many primes exist up to n. The common method is the Sieve of Eratosthenes, which marks multiples while iterating through numbers up to n. This runs in O(n log log n) time and uses an array of size n. Once you know the number of primes p, the number of valid permutations is simply p! * (n - p)!. Compute factorials using modular multiplication with modulus 1e9 + 7. This approach separates the problem into two clear steps: counting primes and counting permutations. It is efficient and scales comfortably within constraints. This solution relies heavily on concepts from math and prime numbers.

Approach 2: Direct Prime Check with Factorials (O(n√n) time, O(1) extra space)

Instead of building a sieve, iterate from 2 to n and check if each number is prime using trial division up to √x. Increment a counter whenever a prime is found. This avoids maintaining an auxiliary array but increases the runtime to O(n√n). After counting primes, compute p! and (n - p)! under modulo just like the previous approach. This method is straightforward and easy to implement, especially in languages where quick loops are cheap. It uses constant auxiliary space and still performs well because n in this problem is relatively small.

Both approaches rely on the combinatorial insight that permutations of primes and non-primes are independent. The final answer is the product of the factorials of their counts. This is essentially a constrained permutation counting problem, closely related to ideas from combinatorics.

Recommended for interviews: Prime counting with a sieve plus factorial computation. Interviewers expect you to recognize that only the number of primes matters, reducing the permutation problem to p! × (n − p)!. Showing the direct prime check first demonstrates understanding, but the sieve-based counting shows stronger algorithmic awareness and better asymptotic performance.

Approach 1: Prime Counting with Factorials

To solve this problem, we need to separate the numbers 1 to n into two groups: prime numbers and non-prime numbers. We can use the Sieve of Eratosthenes to count how many primes are there up to n. Once we know the count of prime numbers, the idea is that those primes must be placed at the prime indices of the permutations. Similarly, non-prime numbers will fill the remaining indices. Therefore, the result will be calculated by multiplying the factorial of the count of prime numbers with the factorial of non-prime numbers.

This Python solution defines a function numPrimeArrangements that calculates the number of valid permutations. It first counts the prime numbers up to n using the count_primes function, which utilizes the Sieve of Eratosthenes algorithm. After determining the number of primes, it calculates the factorials of the number of prime numbers and non-prime numbers, returning their product modulo 10^9 + 7.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(n log log n) due to the Sieve of Eratosthenes, plus O(n) for factorials.
Space Complexity: O(n) for the sieve array.

Try this approach in the editor →

Approach 2: Direct Prime Check with Factorials

Another approach to solve the problem is to directly check each number from 1 to n whether it is a prime or not. Every time a prime is identified, count it, and once we have the counts for primes and non-primes, use the factorial method to compute the permissible permutations.

This Java solution involves a Solution class with a method numPrimeArrangements, which calculates the number of valid permutations by iterating over numbers from 1 to n to determine how many are prime. The isPrime helper method checks primality using basic trial division. Finally, it calculates the factorial of the counts of primes and non-primes using modulo operation for each multiplication to ensure numerical stability.

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O(n√n) due to the naive primality test iterating √n divisions per number.
Space Complexity: O(1) for the constant space usage.

Try this approach in the editor →

Approach 3: Mathematics

First, count the number of prime numbers within the range [1,n], which we denote as cnt. Then, calculate the product of the factorial of cnt and n-cnt to get the answer, remember to perform the modulo operation.

Here, we use the "Sieve of Eratosthenes" to count prime numbers.

If x is a prime number, then multiples of x greater than x, such as 2x, 3x, ... are definitely not prime numbers, so we can start from here.

Let primes[i] indicate whether the number i is a prime number. If it is a prime number, it is true, otherwise it is false.

We sequentially traverse each number i in the range [2,n]. If this number is a prime number, the number of prime numbers increases by 1, and then all its multiples j are marked as composite numbers (except for the prime number itself), that is, primes[j]=false. In this way, at the end of the run, we can know the number of prime numbers.

The time complexity is O(n times log log n).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Prime Counting with Factorials

Time Complexity: O(n log log n) due to the Sieve of Eratosthenes, plus O(n) for factorials.
Space Complexity: O(n) for the sieve array.

Direct Prime Check with Factorials

Time Complexity: O(n√n) due to the naive primality test iterating √n divisions per number.
Space Complexity: O(1) for the constant space usage.

Mathematics—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Prime Counting with Sieve + FactorialsO(n log log n)O(n)Best general solution when you want efficient prime counting and scalable performance
Direct Prime Check + FactorialsO(n√n)O(1)Useful when avoiding extra arrays or when constraints are small

Video Solution

Prime Arrangements | Leetcode #1175 • Techdose • 1,549 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Prime Arrangements easy or hard?
Prime Arrangements is classified as an Easy problem on LeetCode with around a 60% acceptance rate. The main challenge is recognizing that the permutation count depends only on how many primes and non-primes exist up to n.
Prime Arrangements Python/Java solution
The implementation first counts primes up to n, then multiplies factorial(p) and factorial(n−p) under modulo 1e9+7. Python, Java, C++, and JavaScript versions all follow the same logic: prime counting followed by modular factorial multiplication.
How to solve Prime Arrangements in O(n)?
The main work is counting primes up to n and computing factorials. Factorial computation itself is O(n). Prime counting with a sieve is O(n log log n), which is very close to linear and typically considered optimal for this problem.
What is the best approach for Prime Arrangements?
The best approach counts how many prime numbers exist up to n and then computes factorial permutations. If p is the number of primes ≤ n, the answer is p! × (n − p)! modulo 1e9+7. Using the Sieve of Eratosthenes to count primes gives O(n log log n) time and is the most efficient method.
Is Prime Arrangements asked at Google/Amazon/Meta?
Prime Arrangements is commonly used in coding practice platforms and interview preparation because it tests number theory and combinatorics thinking. Similar prime-counting and permutation problems have appeared in interviews at large tech companies such as Amazon and Google.
What data structure is used in Prime Arrangements?
The most common implementation uses a boolean array for the Sieve of Eratosthenes to mark composite numbers. Aside from that, the solution mainly relies on mathematical operations like factorial computation and modular arithmetic.
What is the time complexity of Prime Arrangements?
The optimal solution runs in O(n log log n) time using the Sieve of Eratosthenes to count primes and then computing factorials. A simpler alternative checks each number for primality using trial division, which takes O(n√n) time.

Ready to solve this problem?

Practice Prime Arrangements with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer