## 526. Beautiful Arrangement

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:

1. The number at the ith position is divisible by i.
2. i is divisible by the number at the ith position.

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

Example 1:

```Input: 2
Output: 2
Explanation:
The first beautiful arrangement is [1, 2]:
Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).
Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).
The second beautiful arrangement is [2, 1]:
Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).
Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.
```

Note:

1. N is a positive integer and will not exceed 15.

b'
\n\n

## Solution

\n
\n

#### Approach #1 Brute Force [Time Limit Exceeded]

\n

Algorithm

\n

In the brute force method, we can find out all the arrays that can be formed using the numbers from 1 to N(by creating every possible permutation of the given elements). Then, we iterate over all the elements of every permutation generated and check for the required conditions of divisibility.

\n

In order to generate all the possible pairings, we make use of a function `permute(nums, current_index)`. This function creates all the possible permutations of the elements of the given array.

\n

To do so, `permute` takes the index of the current element as one of the arguments. Then, it swaps the current element with every other element in the array, lying towards its right, so as to generate a new ordering of the array elements. After the swapping has been done, it makes another call to permute but this time with the index of the next element in the array. While returning back, we reverse the swapping done in the current function call.

\n

Thus, when we reach the end of the array, a new ordering of the array\'s elements is generated. The following animation depicts the process of generating the permutations.

\n

!?!../Documents/561_Array.json:1000,563!?!

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . A total of permutations will be generated for an array of length .

\n
• \n
• \n

Space complexity : . The depth of the recursion tree can go upto . array of size is used.

\n
• \n
\n
\n

#### Approach #2 Better Brute Force [Accepted]

\n

Algorithm

\n

In the brute force approach, we create the full array for every permutation and then check the array for the given divisibilty conditions. But this method can be optimized to a great extent. To do so, we can keep checking the elements while being added to the permutation array at every step for the divisibility condition and can stop creating it any further as soon as we find out the element just added to the permutation violates the divisiblity condition.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . refers to the number of valid permutations.

\n
• \n
• \n

Space complexity : . The depth of recursion tree can go upto . Further, array of size is used, where, is the given number.

\n
• \n
\n
\n

#### Approach #3 Backtracking [Accepted]

\n

Algorithm

\n

The idea behind this approach is simple. We try to create all the permutations of numbers from 1 to N. We can fix one number at a particular position and check for the divisibility criteria of that number at the particular position. But, we need to keep a track of the numbers which have already been considered earlier so that they aren\'t reconsidered while generating the permutations. If the current \nnumber doesn\'t satisfy the divisibility criteria, we can leave all the permutations that can be generated with that number at the particular position. This helps to prune the search space of the permutations to a great extent. We do so by trying to place each of the numbers at each position.

\n

We make use of a visited array of size . Here, refers to the number being already placed/not placed in the array being formed till now(True indicates that the number has already been placed).

\n

We make use of a `calculate` function, which puts all the numbers pending numbers from 1 to N(i.e. not placed till now in the array), indicated by a at the corresponding position, and tries to create all the permutations with those numbers starting from the index onwards in the current array. While putting the number, we check whether the number satisfies the divisibility criteria on the go i.e. we continue forward with creating the permutations with the number at the position only if the number and satisfy the given criteria. Otherwise, we continue with putting the next numbers at the same position and keep on generating the permutations.

\n

Look at the animation below for a better understanding of the methodology:

\n

!?!../Documents/526_Beautiful.json:1000,563!?!

\n

Below code is inspired by @shawngao

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . refers to the number of valid permutations.

\n
• \n
• \n

Space complexity : . array of size is used. The depth of recursion tree will also go upto . Here, refers to the given integer .

\n
• \n
\n
\n

Analysis written by: @vinod23

\n
'