Beautiful Arrangement
MedPrompt
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 byi.iis divisible byperm[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] = 1Example 2:
Input: n = 1
Output: 1
Constraints:
1 <= n <= 15
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward way to solve this problem is to generate every possible arrangement of numbers from 1 to n and then check if each arrangement is "beautiful". We can maintain a counter that gets incremented for every beautiful arrangement found.
Algorithm
- Create an array
numscontaining numbers from 1 ton. - Define a recursive function, say
permute(nums, start), which generates all permutations of the subarray starting atstart. - The base case for the recursion is when
startreaches the end of the array. This signifies that a full permutation has been formed. - In the base case, we call a helper function
isBeautiful(nums)to check if the generated permutation satisfies the condition for all indicesifrom 1 ton. - If the permutation is beautiful, we increment a global counter.
- The recursive step involves iterating from the
startindex to the end, swapping the element atstartwith the current element, making a recursive call for the next position (start + 1), and then swapping back to backtrack and explore other possibilities.
Walkthrough
We can implement this using a recursive function that generates all permutations of the numbers.
class Solution { int count = 0; public int countArrangement(int n) { int[] nums = new int[n]; for (int i = 0; i < n; i++) { nums[i] = i + 1; } permute(nums, 0); return count; } private void permute(int[] nums, int start) { if (start == nums.length) { if (isBeautiful(nums)) { count++; } return; } for (int i = start; i < nums.length; i++) { swap(nums, start, i); permute(nums, start + 1); swap(nums, start, i); // backtrack } } private boolean isBeautiful(int[] nums) { for (int i = 0; i < nums.length; i++) { // Problem is 1-indexed, so we check nums[i] against position i+1 if (nums[i] % (i + 1) != 0 && (i + 1) % nums[i] != 0) { return false; } } return true; } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }}Complexity
Time
O(n! * n). There are `n!` possible permutations. For each permutation, we iterate through all `n` elements to check if it's a beautiful arrangement.
Space
O(n). The recursion depth can go up to `n`.
Trade-offs
Pros
Conceptually simple and easy to implement.
Cons
Extremely inefficient. The factorial growth makes it infeasible for
nlarger than 10 or 11.
The brute-force approach is inefficient because it generates complete permutations even if they violate the beautiful arrangement condition early on. We can optimize this by building the permutation position by position and checking the condition at each step. If a number placed at a certain position violates the condition, we can prune this entire branch of the search tree and backtrack, avoiding the generation of many invalid permutations.
Algorithm
- Define a recursive function
calculate(n, pos, visited).posis the current 1-indexed position we are trying to fill. - The base case is when
posbecomes greater thann, which means we have successfully placed numbers in allnpositions. We've found one beautiful arrangement, so we increment our count. - In the recursive step, we iterate through all numbers
ifrom 1 ton. - For each number
i, we check two conditions:- Has
ibeen used already? (!visited[i]) - Does
isatisfy the beautiful condition at positionpos? (i % pos == 0 || pos % i == 0)
- Has
- If both conditions are met, we mark
ias visited, make a recursive call for the next position (pos + 1), and then unmarkias visited to backtrack.
Walkthrough
We use a recursive helper function that tries to place a valid number at each position, one by one. We use a visited array to keep track of the numbers that have already been placed in the permutation.
class Solution { int count = 0; public int countArrangement(int n) { boolean[] visited = new boolean[n + 1]; calculate(n, 1, visited); return count; } private void calculate(int n, int pos, boolean[] visited) { if (pos > n) { count++; return; } for (int i = 1; i <= n; i++) { if (!visited[i] && (i % pos == 0 || pos % i == 0)) { visited[i] = true; calculate(n, pos + 1, visited); visited[i] = false; // backtrack } } }}Complexity
Time
The complexity is difficult to express with a simple formula, but it's roughly proportional to the number of valid partial and full permutations. It's much faster than O(n! * n) and is efficient enough to pass for `n <= 15`.
Space
O(n). We use a `visited` array of size `n+1` and the recursion depth is `n`.
Trade-offs
Pros
Significantly more efficient than brute force due to pruning.
Solves the problem within the given constraints.
Cons
Still exponential in nature.
Can be slower than a dynamic programming solution for this specific problem structure.
Given the small constraint on n (n <= 15), we can suspect a solution with a time complexity related to 2^n. This leads to the idea of using dynamic programming with a bitmask. The bitmask can efficiently represent the set of numbers that have been used in the permutation so far.
Algorithm
- Let
dp[mask]be the number of ways to place the firstknumbers into the firstkpositions, wherekis the number of set bits inmaskand the numbers used are those corresponding to the set bits. - Initialize a
dparray of size2^nwith all zeros, and setdp[0] = 1(representing one way to form an empty arrangement). - Iterate through each
maskfrom 1 to(1 << n) - 1. - For each
mask, determine the number of elements in the set,k = Integer.bitCount(mask). Thiskalso represents the position we are currently trying to fill. - Iterate through each number
jfrom 1 ton. - If number
jis part of the current set (i.e., the(j-1)-th bit is set inmask), we check if it can be placed at positionk. - The condition is
j % k == 0ork % j == 0. - If it's a valid placement, it means we can extend the beautiful arrangements of size
k-1(formed by the numbers inmaskexcludingj) by placingjat positionk. The number of such arrangements isdp[mask ^ (1 << (j-1))]. - We add this to our current state:
dp[mask] += dp[mask ^ (1 << (j-1))]. - After filling the DP table, the final answer is
dp[(1 << n) - 1], which stores the count for arrangements using allnnumbers in allnpositions.
Walkthrough
We define a DP state dp[mask] as the number of beautiful arrangements using a specific subset of numbers from {1, ..., n}. The mask is an integer where the i-th bit is set if the number i+1 is in the subset. The size of the arrangement is simply the number of set bits in the mask.
class Solution { public int countArrangement(int n) { int[] dp = new int[1 << n]; dp[0] = 1; for (int mask = 1; mask < (1 << n); mask++) { int k = Integer.bitCount(mask); for (int j = 0; j < n; j++) { // Check if (j+1)-th number is in the mask if ((mask & (1 << j)) != 0) { int num = j + 1; // Check if 'num' can be placed at position 'k' if (num % k == 0 || k % num == 0) { // Add ways from the previous state (mask without num) dp[mask] += dp[mask ^ (1 << j)]; } } } } return dp[(1 << n) - 1]; }}Complexity
Time
O(n * 2^n). We have a nested loop. The outer loop runs `2^n` times (for each mask), and the inner loop runs `n` times (for each number).
Space
O(2^n). We need a DP array of size `2^n` to store the results for all possible masks.
Trade-offs
Pros
Most efficient time complexity for the given constraints.
Systematic and avoids recursion overhead.
Cons
Higher space complexity compared to backtracking.
The concept of bitmask DP can be less intuitive than a direct recursive approach.
Solutions
Solution
class Solution {public int countArrangement(int N) { int maxn = 1 << N; int[] f = new int[maxn]; f[0] = 1; for (int i = 0; i < maxn; ++i) { int s = 1; for (int j = 0; j < N; ++j) { s += (i >> j) & 1; } for (int j = 1; j <= N; ++j) { if (((i >> (j - 1) & 1) == 0) && (s % j == 0 || j % s == 0)) { f[i | (1 << (j - 1))] += f[i]; } } } return f[maxn - 1]; }}class Solution {public: int n; int ans; vector<bool> vis; unordered_map<int, vector<int>> match; int countArrangement(int n) { this->n = n; this->ans = 0; vis.resize(n + 1); for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) if (i % j == 0 || j % i == 0) match[i].push_back(j); dfs(1); return ans; } void dfs(int i) { if (i == n + 1) { ++ans; return; } for (int j : match[i]) { if (!vis[j]) { vis[j] = true; dfs(i + 1); vis[j] = false; } } }};class Solution: def countArrangement(self, n: int) -> int: def dfs(i): nonlocal ans, n if i == n + 1: ans += 1 return for j in match [i]: if not vis[j]: vis[j] = True dfs(i + 1) vis[j] = False ans = 0 vis = [False] * (n + 1) match = defaultdict(list) for i in range(1, n + 1): for j in range(1, n + 1): if j % i == 0 or i % j == 0: match [i]. append(j) dfs(1) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.