Beautiful Arrangement - Leetcode Solution

The Beautiful Arrangement problem on LeetCode is as follows:

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 beautiful arrangements 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 ≤ 15

Solution:

This problem can be solved using backtracking. We can start with an empty permutation and keep adding elements to it, while making sure that the elements we add satisfy the conditions of being a beautiful arrangement.

Algorithm:

1. Initialize a count variable to 0.
2. Create a helper function backtrack that takes a permutation p and an index i.
3. If i equals n, it means we have successfully formed a beautiful arrangement. Increment the count and return.
4. For each integer j between 1 and n, check if it is already present in the permutation. If not, check if it satisfies the condition of being a beautiful arrangement with respect to the current index i.
5. If j satisfies the condition, add it to the permutation and make a recursive call to backtrack with i+1.
6. After the recursive call, remove the last element from the permutation to backtrack and try another integer.
7. Finally, return the count.

Code:

Here is the Python code for the solution:

class Solution:
    def countArrangement(self, n: int) -> int:
        count = 0
        def backtrack(p, i):
            nonlocal count
            if i == n:
                count += 1
                return
            for j in range(1, n+1):
                if j not in p and (j % (i+1) == 0 or (i+1) % j == 0):
                    p.append(j)
                    backtrack(p, i+1)
                    p.pop()
        backtrack([], 0)
        return count

Time Complexity:

The time complexity of this algorithm is O(k), where k is the number of beautiful arrangements. Since the maximum value of k is not very large (105), the algorithm is considered efficient enough.

Space Complexity:

The space complexity of this algorithm is O(n), since we are using a permutation of size n and a maximum recursion depth of n.

1