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#include <string.h>
class Solution {
public:
int countArrangement(int n) {
std::vector<int> dp(1 << n, -1);
return dfs(dp, 0, n, n);
}
private:
int dfs(std::vector<int>& dp, int mask, int pos, int n) {
if (pos == 0) return 1;
if (dp[mask] != -1) return dp[mask];
int total = 0;
for (int i = 0; i < n; ++i) {
if (!(mask & (1 << i)) && ((pos % (i + 1) == 0) || ((i + 1) % pos == 0))) {
total += dfs(dp, mask | (1 << i), pos - 1, n);
}
}
dp[mask] = total;
return total;
}
};The C++ implementation similarly applies a dynamic programming strategy using bitmasking. Each state is represented by a bitmask, and the function recursively calculates the total number of valid arrangements.