We use analytics and advertising cookies to understand how the site is used and whether our ads on Facebook and Instagram work. They are set only if you accept. See our Privacy Policy for details.
Suppose you have n integers labeled 1 through n. A permutation perm (1-indexed) is beautiful if for every position i, either perm[i] is divisible by i or i is divisible by perm[i].
Return the number of beautiful arrangements you can construct.
A medium backtracking problem, graded against 7 test cases (5 of them hidden).
Systematic exploration of all candidates, abandoning partial ones that cannot work.
Reach for it when you see: "All permutations/combinations/subsets", or constraint puzzles like N-Queens and Sudoku.
More Backtracking problems →Position-by-position backtracking. For each position `pos`, try each unused number `num` where `num % pos === 0` or `pos % num === 0`, mark it used, and recurse. Count every full arrangement.
Time: O(k) where k is the number of valid arrangements (heavily pruned). Space: O(n).
The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.
These apply to the pattern as a whole, not just this problem.