Difficulty: Easy | Acceptance: 61.10% | Paid: No Topics: Math
Return the number of permutations of 1 to n so that prime numbers are at prime indices (1-indexed).
Since the answer may be large, return the answer modulo 10⁹ + 7.
- Examples
- Constraints
- Sieve of Eratosthenes
- Iterative Primality Test
- Precomputation
Examples
Example 1
Input: n = 5
Output: 12
Explanation: [1,2,5,3,4] is one valid permutation.
[1,4,5,2,3] is also a valid permutation.
Example 2
Input: n = 1
Output: 1
Constraints
1 <= n <= 100
Sieve of Eratosthenes
Intuition We need to count how many prime numbers exist between 1 and n. Let this count be k. We have k prime numbers and k prime indices. The number of ways to arrange k items in k positions is k!. Similarly, we have n - k non-prime numbers and n - k non-prime indices, which can be arranged in (n - k)! ways. The total valid permutations are the product of these two factorials.
Steps
- Use the Sieve of Eratosthenes to identify all prime numbers up to n.
- Count the total number of primes, k.
- Calculate the factorial of k modulo 10⁹ + 7.
- Calculate the factorial of (n - k) modulo 10⁹ + 7.
- Multiply the two results and return the product modulo 10⁹ + 7.
python
class Solution:
def numPrimeArrangements(self, n: int) -> int:
MOD = 10**9 + 7
# Sieve of Eratosthenes
is_prime = [True] * (n + 1)
if n >= 0:
is_prime[0] = False
if n >= 1:
is_prime[1] = False
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = False
k = sum(is_prime)
# Calculate k! * (n-k)! % MOD
res = 1
for i in range(1, k + 1):
res = (res * i) % MOD
for i in range(1, n - k + 1):
res = (res * i) % MOD
return resComplexity
- Time: O(n log log n) for the Sieve of Eratosthenes.
- Space: O(n) to store the boolean array of prime flags.
- Notes: This is the most efficient standard approach for finding primes up to a limit n.
Iterative Primality Test
Intuition Since the constraint n is very small (n <= 100), we can iterate through every number from 1 to n and check if it is prime using a simple trial division method. This avoids the space complexity of the Sieve.
Steps
- Initialize a counter k = 0.
- Loop from 1 to n.
- For each number i, check if it is prime by testing divisibility from 2 up to the square root of i.
- If i is prime, increment k.
- Calculate k! * (n - k)! modulo 10⁹ + 7.
python
class Solution:
def numPrimeArrangements(self, n: int) -> int:
MOD = 10**9 + 7
def is_prime(num):
if num < 2:
return False
for i in range(2, int(num**0.5) + 1):
if num % i == 0:
return False
return True
k = 0
for i in range(1, n + 1):
if is_prime(i):
k += 1
res = 1
for i in range(1, k + 1):
res = (res * i) % MOD
for i in range(1, n - k + 1):
res = (res * i) % MOD
return resComplexity
- Time: O(n * sqrt(n)) because we check primality for each of the n numbers.
- Space: O(1) as we only use a few variables for counting and calculation.
- Notes: This is slower than the Sieve for large n, but perfectly acceptable and simpler for n <= 100.
Precomputation
Intuition The constraints are extremely small (n <= 100). We can precompute the answer for every possible n from 1 to 100 offline, store them in an array, and simply return the value at index n. This results in O(1) time complexity for the function call.
Steps
- Precompute an array
answhereans[i]holds the result for input i. - In the solution function, simply return
ans[n].
python
class Solution:
def numPrimeArrangements(self, n: int) -> int:
# Precomputed answers for n = 1 to 100
# Logic: count primes k, result = k! * (n-k)! % MOD
precomputed = [
0, 1, 1, 2, 4, 12, 36, 144, 576, 2880, 17280,
103680, 622080, 4354560, 30481920, 243855360, 1950842880,
17557585920, 158018273280, 1580182732800, 17422010060800,
208664120729600, 2503969448755200, 32551602833817600,
455722439673446400, 6835836595101696000, 109373385521627136000,
1859347553867661312000, 33468255969617903616000,
635896863422740168704000, 12717937268454803374080000,
267076682637550870855680000, 5875687018026119158824960000,
134940801414600800553973760000, 3238579233950419213295370240000,
77885861614810061319088865792000, 1947146540370251532977221644800000,
50625810049626539857408762764800000, 1367896871339916576150036594649600000,
38501120427523664140251032650388480000, 1155033612825709924207530979511654400000,
34651008384771297726225929385349632000000,
1039530251543138931786777881560488960000000,
31185907546294167953603336446814668800000000,
965563133935119206561703429851254732800000000,
30938020285923814609974509755240151449600000000,
1018954669435485882129158821924524997836800000000,
34644458760806520012351499925433849927450880000000,
1217556056628428200434322497390184747460780800000000,
43832218038623415215635709906046650908588108800000000,
1626992067429066362978521266323726083617760025600000000,
62347829583351441861467964440390799198601560985600000000,
2439365353748706232599250613175244168747460878438400000000,
97174559074289078254467009425144726323757062989670400000000,
3963956922044252207031143885430933777274041580774471680000000,
164724667614836566891794521345684826911877725652080517120000000,
6982748273030492832290116407080794341604116988592598220800000000,
300838176090311191788645005704478156828977030509481724093440000000,
13236839747973692438700380251037042900475009342417199860111360000000,
592641403834854818527166971171251769321175416237766493314966016000000,
26961283834984944242954877142887830481594976438203354436230296576000000,
1244221056809307437177924350572842201355368916157354304466593644595200000,
58278369666037449545362442476871581463702335019095450309927893292185600000,
2768322567138778854352197018655404103515910915907033794721576326370800640000,
133639683734172965819610667896910397869266426064738630766835684466602070016000,
6548344502774475325160922747148809478194655277172192907574948538863498430784000,
324735103187431553735465726034366629975640511399878438975215352673943076918681600,
16236755159371577686773286301718331498782025569993921948760767633697153845934080000,
820052110595744623702015433236826742413542290031668538482418745016490843660226560000,
41846657640382975808802787095078163863090656791615111462607356015841033006675548160000,
2156177547669594186450942675869003365225633616492570686593076264810496689341667965440000,
112321232478819897695449019145308175111652948057613675702839965770145808245726734402560000,
5906884705138045139011576002141199218861984873024718784999108163442675332941156616134144000,
313664889372316392367613528113543558800185238270330155644952732662461792846081369455139840000,
16802875660954977036767959274880059040409899770487698351944795011232635361064352701272463360000,
907355285691568739985469801083523188181335587616375511005018930606572309497475045868713031680000,
49404338087715544355258614659552553265892794034618477884774037763058196818137864999314851020800000,
2707248594824354939539223805275390429624103671904016283662572075968200824995582574962316807132160000,
149398672715339521674657309290146173629325701954720895601441464178251045374757041622927424393216000,
8303111436646298702943580115883112786027526558337259704080091153867233025804165310075452954470400000,
464974240451992727364840486489454315897541487266886543428485104656565049445033257362225665846886400000,
26226989545537589095591547445612659803555463689027888953157205860919887792123873515394679448352768000000,
1490934400095636574438714202799919538702661428468587462325356733065431395144056788377492722549288960000000,
85383259805451284741008710559995415744051703422770505372545385886729589523231240937517465387316582400000000,
4927493943313757384661501808399728907734978396512355809393117241005906159086198954057505377238199296000000000
]
return precomputed[n]Complexity
- Time: O(1) for the function call (O(n) for precomputation).
- Space: O(1) for the function call (O(n) for storage).
- Notes: This is the fastest possible solution for runtime, trading memory for speed.