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 C dynamic programming solution with bitmasks efficiently explores all possible permutations and uses memoization to avoid redundant calculations, by storing results of subproblems in the dp array.