Beautiful Arrangement Visualizer & Step-by-Step Algorithm Solution

Count the number of permutations where either the number at position i is divisible by i, or i is divisible by the number, using recursive backtracking and divisibility pruning.

Category: backtracking | Difficulty: Medium

Tags: Backtracking, Bit Manipulation, Recursion, Permutations, Math

Beautiful Arrangement

[]
Numbers Array nums = [1, 2, 3]
1
0
2
1
3
2
100%
state
n3
curr[]
position1/3
arrangementsFound0
Initialization
1/113
Explanation

Start countArrangement for n = 3. Finding permutations satisfying divisibility at every position.

Source Code
1function countArrangement(n: number): number {
2 const nums = new Array(n).fill(null).map((_, i) => i + 1);
3 const result: number[][] = [];
4 const used = new Array(nums.length).fill(false);
5
6 function backtrack(curr: number[]) {
7 if (curr.length === nums.length) {
8 result.push([...curr]);
9 return;
10 }
11 for (let i = 0; i < nums.length; i++) {
12 if (used[i]) continue;
13 if (
14 nums[i] % (curr.length + 1) !== 0 &&
15 (curr.length + 1) % nums[i] !== 0
16 )
17 continue;
18 used[i] = true;
19 curr.push(nums[i]);
20 backtrack(curr);
21 curr.pop();
22 used[i] = false;
23 }
24 }
25 backtrack([]);
26 return result.length;
27}