## Similar Problems

Similar Problems not available

# Beautiful Arrangement - Leetcode Solution

## Companies:

LeetCode: Beautiful Arrangement Leetcode Solution

Difficulty: Medium

Topics: backtracking bit-manipulation array dynamic-programming

Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position (1 <= i <= N) in this array:

The number at the ith position is divisible by i.

i is divisible by the number at the ith position.

Now given N, how many beautiful arrangements can you construct?

#### Example 1:

Input: 3

Output: 3

Explanation:

The accepted permutations are: [[1,2,3], [3,2,1], [2,1,3]].

if we take [3,2,1], the first number 3 at index i = 1, is divisible by it’s index, the second number 2 is also divisible by it’s index i = 2. For the last number 1, at index i = 3, it divides it’s index completely.

**Note:**

N is a positive integer and will not exceed 15.

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:

- Initialize a count variable to 0.
- Create a helper function backtrack that takes a permutation p and an index i.
- If i equals n, it means we have successfully formed a beautiful arrangement. Increment the count and return.
- 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.
- If j satisfies the condition, add it to the permutation and make a recursive call to backtrack with i+1.
- After the recursive call, remove the last element from the permutation to backtrack and try another integer.
- 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.

## Beautiful Arrangement Solution Code

`1`