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.
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]; }}Video 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.