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.
1def countArrangement(n):
2 def count(i, x):
3 if i < 2:
4 return 1
5 total = 0
6 for j in range(n):
7 if not (x & (1 << j)) and ((i % (j + 1) == 0) or ((j + 1) % i == 0)):
8 total += count(i - 1, x | (1 << j))
9 return total
10 return count(n, 0)This solution uses bitmasking to mark the numbers that have been used. It recursively checks each position with available numbers. If a number can be placed at a position according to the rules, it tries to place the next number. If a full beautiful arrangement is achieved, it counts it.
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.