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.
1function countArrangement(n) {
2 function helper(pos, visited) {
3 if (pos > n) return 1;
4 let total = 0;
5 for (let i = 1; i <= n; i++) {
6 if (!visited[i] && (i % pos === 0 || pos % i === 0)) {
7 visited[i] = true;
8 total += helper(pos + 1, visited);
9 visited[i] = false;
10 }
11 }
12 return total;
13 }
14 return helper(1, Array(n + 1).fill(false));
15}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.
1
This Python solution uses a top-down dynamic programming approach with memoization. The function dfs uses a bitmask to denote which integers have been placed, and iteratively places integers satisfying the beautiful arrangement condition.