hardBacktrackingPure DSA~30 min
Count Arrangements Where Position Divides Value
Count permutations of 1..n such that at every position i (1-indexed), either the value is divisible by i or i is divisible by the value.
Problem
Given an integer n, consider permutations of the numbers 1..n. A permutation perm is 'beautiful' if for every 1 <= i <= n, perm[i] is divisible by i or i is divisible by perm[i]. Return the number of beautiful arrangements.
Input
A single integer n.
Output
An integer: the count of beautiful arrangements.
Constraints
- 1 <= n <= 15
- Positions are 1-indexed.
- Each value 1..n is used exactly once.
Examples
Example 1
Input
n = 2
Output
2
[1,2] and [2,1] both satisfy the divisibility rule.
Example 2
Input
n = 1
Output
1
The single arrangement is trivially beautiful.