Beautiful Arrangement
Medium · Backtracking · Array · Dynamic Programming · Backtracking · Bit Manipulation · Bitmask
Problem
You have the integers 1 through n. A permutation perm of them, numbered from position 1, is beautiful if for every position i from 1 to n at least one of these holds:
- perm[i] is divisible by i, or
- i is divisible by perm[i].
Given n, return how many beautiful permutations there are.
Examples
Input: n = 3 Output: 3
[1,2,3], [2,1,3] and [3,2,1] work. [1,3,2] fails: at position 2, neither 3 nor 2 divides the other.
Input: n = 4 Output: 8
Exactly 8 of the 24 permutations satisfy the rule at every position.
Input: n = 1 Output: 1
The single permutation [1] is beautiful.
Constraints
- 1 <= n <= 15
Approaches
- Baseline: backtracking position by position — time O(k) where k is the number of valid partial arrangements (well under n!), space O(n)
Follow-up
Why is the mask enough state? Positions are filled in order, so a mask with k bits set always means positions 1..k are filled, and what remains possible depends only on which values are left, not on where the used ones went. That is what lets arrangements that used the same values merge, turning n! orders into 2^n states.
Related problems
Start free on Cariara · Coding problems · System design studio
