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 bool[n + 1]);
4 }
5
6 private int Count(int n, int pos, bool[] 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 C# solution follows the same backtracking mechanism as other languages explained above, using a boolean array to track visited indices within a recursive function to count each beautiful arrangement.
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.