Beautiful Arrangement
Asked at Rippling
Problem
Given an integer n, count the number of beautiful arrangements where placing numbers 1 to n in positions 1 to n, each number at position i is divisible by i or i is divisible by the number. This tests backtracking with bitmask optimization.
Asked At
| Company | Difficulty | |
|---|---|---|
| Rippling | Medium | View all Rippling questions → |
How to Think About It
Brute force: generate all n! permutations and check each for the beautiful property. That's O(n! * n) - far too slow for n up to 15.
Key insight: use backtracking with pruning. At each position, try all unused numbers that satisfy the divisibility condition. Skip numbers that don't divide the position and whose position doesn't divide them. This prunes most branches.
Bitmask optimization: represent the set of used numbers as a bitmask. This makes the state compact (2^n states) and enables memoization. dp[mask] = number of ways to fill positions using the numbers in mask.
Memoization approach: define dfs(pos, mask) where pos is the current position to fill and mask is which numbers are used. For each unused number that satisfies the condition, recurse. Cache results by (pos, mask).
Visual walkthrough for n=3:
Position 1: try 1 (1%1==0, ok), 2 (2%1==0, ok), 3 (3%1==0, ok).
Try pos=1, num=1. mask={1}. pos=2: try 2 (2%2==0, ok), 3 (3%2!=0 and 2%3!=0, skip).
Try pos=2, num=2. mask={1,2}. pos=3: try 3 (3%3==0, ok).
pos=3, num=3. mask={1,2,3}. All positions filled! Count=1.
Backtrack. Try pos=2, num=3. mask={1,3}. pos=3: try 2 (2%3!=0 and 3%2!=0, skip). Dead end.
Try pos=1, num=2. mask={2}. pos=2: try 1 (2%1==0, ok), 3 (3%2!=0, skip).
Try pos=2, num=1. mask={1,2}. pos=3: try 3 (3%3==0). Count=2.
Try pos=2, num=3. Dead end (3%2!=0).
Try pos=1, num=3. mask={3}. pos=2: try 1 (2%1==0, ok), 2 (2%2==0, ok).
pos=2, num=1: pos=3, try 2. 3%2!=0, 2%3!=0. Dead end.
pos=2, num=2: pos=3, try 1. 3%1==0, ok! Count=3.
Result: 3.
Edge cases: n=1 (return 1), n=2 (return 2: [1,2] and [2,1]).
Optimal Approach
Use backtracking with bitmask memoization.
- Define dfs(pos, mask): number of beautiful arrangements to fill positions from pos to n, given the set of used numbers in mask.
- Base case: if pos > n, return 1 (all positions filled).
- For each number i from 1 to n:
- If i is not in mask AND (i % pos == 0 OR pos % i == 0):
- Set bit i in mask, recurse on pos+1.
- Sum all valid recursive results.
- Memoize by (pos, mask).
Walkthrough for n=3:
- dfs(1, 000): try 1, 2, 3.
- dfs(2, 001): try 2 (2%2==0). dfs(3, 011): try 3 (3%3==0). dfs(4, 111) = 1. Total += 1.
- dfs(2, 010): try 1 (2%1==0). dfs(3, 011): try 3. dfs(4, 111) = 1. Total += 1.
- dfs(2, 100): try 1 (2%1==0). dfs(3, 101): try 2 (3%2!=0, skip). try 3 (already used). Dead. Total += 0.
- dfs(2, 100): try 2 (2%2==0). dfs(3, 110): try 1 (3%1==0). dfs(4, 111) = 1. Total += 1.
- Result: 3.
Time: O(n * 2^n) states, each O(n) to enumerate. Space: O(n * 2^n) for memoization.
What Trips People Up in Real Interviews
Trying to generate all permutations and check each one. That's O(n!) and will time out for n >= 12. Use backtracking with pruning or bitmask DP.
Forgetting the divisibility check goes both ways. The condition is: position i divides number OR number divides position i. You need to check both i % num == 0 and num % i == 0.
Using 0-indexed positions instead of 1-indexed. The problem uses 1-based indexing: position 1 through n. If you use 0-indexed, adjust the divisibility check accordingly.
Not memoizing the backtracking. Without memoization, the same (position, mask) state can be reached through different paths, leading to exponential recomputation. Memoization brings it to O(n * 2^n).
Off-by-one in the bitmask. If using bit i to represent number i, make sure bit 0 is unused (numbers start from 1) or shift by 1. Mixing up the bit representation causes wrong results.
Solution Code
def countArrangement(n):
memo = {}
def dfs(pos, mask):
if pos > n:
return 1
if (pos, mask) in memo:
return memo[(pos, mask)]
count = 0
for i in range(1, n + 1):
if not (mask & (1 << i)) and (i % pos == 0 or pos % i == 0):
count += dfs(pos + 1, mask | (1 << i))
memo[(pos, mask)] = count
return count
return dfs(1, 0)Frequently Asked Questions
What is the Beautiful Arrangement problem?
Given an integer n, count the number of beautiful arrangements where placing numbers 1 to n in positions 1 to n, each number at position i is divisible by i or i is divisible by the number. This tests backtracking with bitmask optimization.
How do you solve Beautiful Arrangement?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Beautiful Arrangement?
Beautiful Arrangement is asked at Rippling. It is a medium difficulty problem.
What are common mistakes on Beautiful Arrangement?
- Trying to generate all permutations and check each one. That's `O(n!)` and will time out for n >= 12. Use backtracking with pruning or bitmask DP.
- Forgetting the divisibility check goes both ways. The condition is: position i divides number OR number divides position i. You need to check both `i % num == 0` and `num % i == 0`.
- Using 0-indexed positions instead of 1-indexed. The problem uses 1-based indexing: position 1 through n. If you use 0-indexed, adjust the divisibility check accordingly.
- Not memoizing the backtracking. Without memoization, the same (position, mask) state can be reached through different paths, leading to exponential recomputation. Memoization brings it to `O(n * 2^n)`.
- Off-by-one in the bitmask. If using bit i to represent number i, make sure bit 0 is unused (numbers start from 1) or shift by 1. Mixing up the bit representation causes wrong results.