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 <stdbool.h>
2
3int countArrangementUtil(int n, int *visited, int pos) {
4 if (pos > n) return 1;
5 int count = 0;
6 for (int i = 1; i <= n; ++i) {
7 if (!visited[i] && (i % pos == 0 || pos % i == 0)) {
8 visited[i] = true;
9 count += countArrangementUtil(n, visited, pos + 1);
10 visited[i] = false;
11 }
12 }
13 return count;
14}
15
16int countArrangement(int n) {
17 int visited[n + 1];
18 for (int i = 0; i <= n; i++) visited[i] = false;
19 return countArrangementUtil(n, visited, 1);
20}This C solution uses a similar backtracking approach as described above, where you recursively attempt to place each number in the current position and mark it in the visited array. The function counts the valid arrangements and returns the total count.
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.