Suppose you have n integers labeled 1 through n. A permutation of those n integers perm (1-indexed) is considered a beautiful arrangement if for every i (1 <= i <= n), either of the following is true:
perm[i] is divisible by i.i is divisible by perm[i].Given an integer n, return the number of the beautiful arrangements that you can construct.
Example 1:
Input: n = 2
Output: 2
Explanation:
The first beautiful arrangement is [1,2]:
- perm[1] = 1 is divisible by i = 1
- perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
- perm[1] = 2 is divisible by i = 1
- i = 2 is divisible by perm[2] = 1
Example 2:
Input: n = 1 Output: 1
Constraints:
1 <= n <= 15In #526 Beautiful Arrangement, we need to count permutations of numbers from 1..n such that for every position i, either perm[i] % i == 0 or i % perm[i] == 0. The most effective strategy is backtracking with pruning. We place numbers position by position and only choose values that satisfy the divisibility rule for that index. By tracking used numbers and skipping invalid candidates early, the search space reduces significantly.
An optimized variant uses bitmask dynamic programming. A bitmask represents which numbers have already been used, and the number of set bits determines the current position. The DP state stores how many valid arrangements can be formed from that mask. Precomputing valid numbers for each position further speeds up transitions.
Backtracking works well because n ≤ 15, while the bitmask DP approach provides a structured solution with memoization. The optimized DP solution typically runs in about O(n · 2^n) time with O(2^n) space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Backtracking with Pruning | O(n!) worst case, but heavily pruned in practice | O(n) |
| Bitmask Dynamic Programming | O(n × 2^n) | O(2^n) |
Knowledge Center
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 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.
1def
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems similar to Beautiful Arrangement appear in technical interviews because they test backtracking, recursion, and bitmask techniques. While the exact problem may not always appear, the pattern of constrained permutation generation is common in FAANG-style interviews.
The optimal approach typically uses bitmask dynamic programming or backtracking with pruning. Bitmask DP tracks which numbers are already used and computes the number of valid permutations efficiently. This reduces redundant work and runs in roughly O(n × 2^n) time.
Backtracking works well because the constraints allow strong pruning. At each position, you only try numbers that satisfy the divisibility condition, which eliminates many permutations early. Since n is at most 15, the reduced search space makes the approach practical.
A bitmask is commonly used to represent which numbers are already included in the permutation. Combined with a DP array or memoization map, it allows efficient state transitions and avoids recomputation of subproblems.
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.