Sponsored
Sponsored
The idea is to generate permutations of the numbers from 1 to n and check if each permutation is a beautiful arrangement. This can be efficiently done using backtracking. While generating permutations, we can directly test the divisibility conditions to ensure they form a beautiful arrangement.
Time Complexity: O(k), where k are the valid permutations (worst-case roughly n!).
Space Complexity: O(n) due to the recursion stack.
The JavaScript solution implements the backtracking using a helper function and a boolean array to mark numbers that are already used, incrementally counting valid permutations by exploring each depth-first search path.
This approach involves using dynamic programming (DP) with bitmasking to efficiently count beautiful arrangements. By representing the set of visited numbers as a bitmask and using memoization, we can avoid redundant calculations.
Time Complexity: O(n * 2^n) due to bitmask permutations.
Space Complexity: O(2^n) for the DP cache plus recursion stack.
1function countArrangement(n) {
2 const dp = new Array(1 << n).fill(-1);
3
4 function dfs(mask, pos) {
5 if (pos === 0) return 1;
6 if (dp[mask] !== -1) return dp[mask];
7
8 let total = 0;
9 for (let i = 0; i < n; i++) {
10 if (!(mask & (1 << i)) && ((pos % (i + 1) === 0) || ((i + 1) % pos === 0))) {
11 total += dfs(mask | (1 << i), pos - 1);
12 }
13 }
14 dp[mask] = total;
15 return total;
16 }
17
18 return dfs(0, n);
19}This JavaScript code employs dynamic programming with a bitmask-based approach. It recursively calculates the number of valid arrangements using memoization.