Description
Suppose you have n integers from 1 to n. A permutation perm is beautiful if for every i: perm[i] is divisible by i, or i is divisible by perm[i]. Return the number of beautiful arrangements.
Examples
Input:
n = 2Output:
2Explanation:
[1,2] and [2,1] are both beautiful.
Input:
n = 1Output:
1Explanation:
With n = 1, there's only one permutation [1]. Since 1 is divisible by 1, this arrangement is beautiful.
Input:
n = 4Output:
8Explanation:
The 8 beautiful arrangements are: [2,1,4,3], [3,2,1,4], [4,1,2,3], [2,4,1,3], [3,4,1,2], [4,2,1,3], [1,2,3,4], [1,4,3,2]. In each, every position i has perm[i] divisible by i or i divisible by perm[i].
Constraints
- •
1 ≤ n ≤ 15