Abstract / Summary

Count the ways to arrange numbers so that prime positions have prime numbers and non-prime positions have non-prime numbers.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 62% (70k+ submissions).

Typical patterns to solve this problem:

• Math

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a method that computes the number of valid permutations of the first n positive integers where prime numbers occupy prime-indexed positions. The result is returned modulo 10⁹ + 7. The algorithm proceeds in three logical phases: identification of prime values within the range 1…n, calculation of factorials for the counts of prime and non-prime numbers, and the final modular multiplication.

Prime Identification

The method begins by storing a static list of all prime numbers up to 100. This list serves as a lookup table, allowing the algorithm to determine primality through a simple membership test rather than performing division-based checks for each candidate.

primes = [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
           41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
           83, 89, 97 ]

A counter numprime is initialized to zero. The loop iterates from 1 through n (inclusive). For each integer i, the expression i in primes checks whether i appears in the pre-computed list. When the test succeeds, numprime is incremented.

numprime = 0
for i in range(1, n+1):   # slow but simple
    if i in primes:
        numprime += 1

Because the list contains every prime up to 100, the loop correctly counts primes for any n ≤ 100. For values of n greater than 100, the membership test will never succeed beyond the largest entry, effectively treating all numbers above 97 as non-prime. This behavior aligns with the problem constraints that limit n to at most 100.

Deriving the Complement Count

After the loop finishes, the number of non-prime integers is obtained by subtracting the prime count from the total count n. This simple arithmetic yields the size of the complementary set without requiring a separate scan.

notprime = n - numprime

The calculation gracefully handles edge conditions such as n = 0 or n = 1. In those cases numprime remains zero, and notprime equals n, preserving the mathematical relationship needed for the subsequent factorial step.

Factorial Computation and Modulo Reduction

The final result is the product of two factorials: one for the prime count and one for the non-prime count. The built-in factorial function from Python’s standard library is employed, leveraging its highly optimized C implementation.

return (factorial(numprime) * factorial(notprime)) % (10**9 + 7)

Multiplying the two factorial values first and then applying the modulus ensures that the intermediate product fits within Python’s arbitrary-precision integer range while still delivering the required modular result. The modulo constant 10**9 + 7 is a prime modulus commonly used to avoid overflow in combinatorial calculations.

Edge Cases Handled

When n equals zero, the loop body never executes, leaving numprime at zero. Consequently notprime also becomes zero, and the factorial of zero is defined as one. The expression therefore returns 1, which is the mathematically correct count of permutations for an empty set.

For n equal to one, the loop checks the single value 1, which is not present in the prime list, so numprime stays zero and notprime becomes one. The factorials evaluate to 1 and 1, and the method again returns 1.

If n reaches the upper bound of the allowed range (typically 100), the prime list fully covers all possible prime values, guaranteeing accurate counting. The algorithm’s reliance on the pre-computed list eliminates the need for dynamic primality testing, thereby sidestepping potential off-by-one errors that can arise in iterative sieve implementations.

Performance Optimizations Observed

The most notable optimization is the use of a static prime lookup table. By avoiding repeated division or sieve construction, the code reduces the per-iteration cost to a constant-time membership test. Although the in operator on a list performs a linear scan, the list’s length is limited to twenty-five elements, making the overhead negligible for the problem’s scale.

Utilizing Python’s built-in factorial function provides a further speed advantage. The function is implemented in C and benefits from internal caching and fast multiplication algorithms, delivering factorial values far more efficiently than a naïve Python loop would.

Finally, the modular reduction is performed only once after the multiplication, minimizing the number of modulo operations. This approach takes advantage of Python’s ability to handle large integers without immediate overflow, allowing the intermediate product to be computed directly before the final reduction.

Imagine you have a long row of empty chairs, and you want to seat some special guests in them. Some of these guests are prime numbers, which are like magical numbers that can only be divided by themselves and one. First, this code counts how many chairs there are in total and figures out how many of those chairs can be filled by these magical prime numbers. The remaining chairs get the regular numbers. To find out how many different ways the guests can sit, the code multiplies the number of ways to arrange the prime numbers by the number of ways to arrange the regular numbers. Finally, it uses a very big number to chop the answer into a smaller, tidier piece so that it fits neatly inside the computer.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++			Python	Java		TS
	WalkCCC	C++			Python	Java
	leetcode.ca	C++			Python	Java	Go
	Progiez	C++			Python	Java
github	BigEggStudy			C#
	black-shadows	C++
	charles-wangkai					Java
	everthis		JS
	fsq	C++
	halfrost						Go
	JoshCrozier		JS
	keineahnung2345	C++
	lkwq007				Python
	suxrobGM			C#
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
suxrobGM	C#

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality