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.
1#include <vector>
2
3class Solution {
4public:
5 int countArrangement(int n) {
6 std::vector<int> visited(n + 1, 0);
7 return count(n, 1, visited);
8 }
9
10private:
11 int count(int n, int pos, std::vector<int>& visited) {
12 if (pos > n) return 1;
13 int total = 0;
14 for (int i = 1; i <= n; ++i) {
15 if (!visited[i] && (i % pos == 0 || pos % i == 0)) {
16 visited[i] = 1;
17 total += count(n, pos + 1, visited);
18 visited[i] = 0;
19 }
20 }
21 return total;
22 }
23};The C++ solution utilizes a recursive backtracking approach using a vector to track visited numbers. Each recursive call attempts to place a valid number in the current position, counting the valid arrangements.
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.