Hex.*

LC1175 - Prime Arrangements

Posted on In
Leetcode: 146/2658 (58+70+18)

Description

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

Solution

  1. First get the number of prime numbers in n numbers
  2. Then get the number of non-prime numbers = n - the number of prime numbers
  3. The answer is obtained by multiplying the number of permutations of prime numbers by the number of permutations of non-primes.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# O(n) time | O(n) space
class Solution:
    def numPrimeArrangements(self, n: int) -> int:
        primecnt = 0
        mod = 1e9+7
        ans = 1
        for i in range(2, n+1):
            for j in range(2, i):
                if i % j == 0:
                    break
            else:
                primecnt+=1
        
        for i in range(1, primecnt+1):
            ans *= i
            ans %= mod
        
        for i in range(1, n-primecnt+1):
            ans *= i 
            ans %= mod
        return int(ans)

How to find prime numbers in a range

1
2
3
4
5
6
7
8
9
10
num = [];
n = 100
for i in range(2, n):
    for j in range(2, i):
        if (i % j == 0):
            break
		# This else executes only if break is NEVER reached and loop terminated after all iterations.
    else:
        num.append(i)
print(num)

Factorial

For Loop

1
2
3
4
5
6
7
8
ans = 1
mod = 1e9+7
n = 10
for i in range(1, n+1):
		ans *= i
		# if the number is too large
		ans %= mod
print(ans)

Reduce Function

1
2
3
4
from functools import reduce
n = 10
ans = reduce(lambda x, y: x*y, range(1, n+1))
print(ans)

Recursion

1
2
3
4
5
6
7
8
def factorial(n):
		if n == 0 or n ==1:
				return 1
		else:
				return (n*factorial(n-1))

ans = factorial(10)
print(ans)