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.
1public class Solution {
2 public int countArrangement(int n) {
3 return count(n, 1, new boolean[n + 1]);
4 }
5
6 private int count(int n, int pos, boolean[] visited) {
7 if (pos > n) return 1;
8 int total = 0;
9 for (int i = 1; i <= n; i++) {
10 if (!visited[i] && (i % pos == 0 || pos % i == 0)) {
11 visited[i] = true;
12 total += count(n, pos + 1, visited);
13 visited[i] = false;
14 }
15 }
16 return total;
17 }
18}The Java solution employs a backtracking technique with a boolean array to mark numbers that have been used in the current permutation. It checks and counts if a number can be placed at the current position, proceeding recursively.
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.