Description#
Suppose you have n integers labeled 1 through n. A permutation of those n integers perm (1-indexed) is considered a beautiful arrangement if for every i (1 <= i <= n), either of the following is true:
perm[i] is divisible by i.i is divisible by perm[i].
Given an integer n, return the number of the beautiful arrangements that you can construct.
Example 1:
Input: n = 2
Output: 2
Explanation:
The first beautiful arrangement is [1,2]:
- perm[1] = 1 is divisible by i = 1
- perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
- perm[1] = 2 is divisible by i = 1
- i = 2 is divisible by perm[2] = 1
Example 2:
Input: n = 1
Output: 1
Constraints:
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution:
def countArrangement(self, n: int) -> int:
def dfs(i):
nonlocal ans, n
if i == n + 1:
ans += 1
return
for j in match[i]:
if not vis[j]:
vis[j] = True
dfs(i + 1)
vis[j] = False
ans = 0
vis = [False] * (n + 1)
match = defaultdict(list)
for i in range(1, n + 1):
for j in range(1, n + 1):
if j % i == 0 or i % j == 0:
match[i].append(j)
dfs(1)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| class Solution {
private int n;
private int ans;
private boolean[] vis;
private Map<Integer, List<Integer>> match;
public int countArrangement(int n) {
this.n = n;
ans = 0;
vis = new boolean[n + 1];
match = new HashMap<>();
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i % j == 0 || j % i == 0) {
match.computeIfAbsent(i, k -> new ArrayList<>()).add(j);
}
}
}
dfs(1);
return ans;
}
private void dfs(int i) {
if (i == n + 1) {
++ans;
return;
}
if (!match.containsKey(i)) {
return;
}
for (int j : match.get(i)) {
if (!vis[j]) {
vis[j] = true;
dfs(i + 1);
vis[j] = false;
}
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
public:
int n;
int ans;
vector<bool> vis;
unordered_map<int, vector<int>> match;
int countArrangement(int n) {
this->n = n;
this->ans = 0;
vis.resize(n + 1);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (i % j == 0 || j % i == 0)
match[i].push_back(j);
dfs(1);
return ans;
}
void dfs(int i) {
if (i == n + 1) {
++ans;
return;
}
for (int j : match[i]) {
if (!vis[j]) {
vis[j] = true;
dfs(i + 1);
vis[j] = false;
}
}
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| func countArrangement(n int) int {
ans := 0
match := make(map[int][]int)
for i := 1; i <= n; i++ {
for j := 1; j <= n; j++ {
if i%j == 0 || j%i == 0 {
match[i] = append(match[i], j)
}
}
}
vis := make([]bool, n+1)
var dfs func(i int)
dfs = func(i int) {
if i == n+1 {
ans++
return
}
for _, j := range match[i] {
if !vis[j] {
vis[j] = true
dfs(i + 1)
vis[j] = false
}
}
}
dfs(1)
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| function countArrangement(n: number): number {
const vis = new Array(n + 1).fill(0);
const match = Array.from({ length: n + 1 }, () => []);
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= n; j++) {
if (i % j === 0 || j % i === 0) {
match[i].push(j);
}
}
}
let res = 0;
const dfs = (i: number, n: number) => {
if (i === n + 1) {
res++;
return;
}
for (const j of match[i]) {
if (!vis[j]) {
vis[j] = true;
dfs(i + 1, n);
vis[j] = false;
}
}
};
dfs(1, n);
return res;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| impl Solution {
fn dfs(i: usize, n: usize, mat: &Vec<Vec<usize>>, vis: &mut Vec<bool>, res: &mut i32) {
if i == n + 1 {
*res += 1;
return;
}
for &j in mat[i].iter() {
if !vis[j] {
vis[j] = true;
Self::dfs(i + 1, n, mat, vis, res);
vis[j] = false;
}
}
}
pub fn count_arrangement(n: i32) -> i32 {
let n = n as usize;
let mut vis = vec![false; n + 1];
let mut mat = vec![Vec::new(); n + 1];
for i in 1..=n {
for j in 1..=n {
if i % j == 0 || j % i == 0 {
mat[i].push(j);
}
}
}
let mut res = 0;
Self::dfs(1, n, &mat, &mut vis, &mut res);
res
}
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int countArrangement(int N) {
int maxn = 1 << N;
int[] f = new int[maxn];
f[0] = 1;
for (int i = 0; i < maxn; ++i) {
int s = 1;
for (int j = 0; j < N; ++j) {
s += (i >> j) & 1;
}
for (int j = 1; j <= N; ++j) {
if (((i >> (j - 1) & 1) == 0) && (s % j == 0 || j % s == 0)) {
f[i | (1 << (j - 1))] += f[i];
}
}
}
return f[maxn - 1];
}
}
|
