## The Problem

Suppose you have

`n`

integers labeled`1`

through`n`

. A permutation of those`n`

integers`perm`

(1-indexed) is considered abeautiful arrangementif for every`i (1 <= i <= n)`

,eitherof the following is true:

`perm[i]`

is divisible by`i`

.`i`

is divisible by`perm[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] = 1
```

**Example 2:**

```
Input: n = 1
Output: 1
```

## My Tests

```
import pytest
from .Day3 import Solution
s = Solution()
@pytest.mark.parametrize("input,expected", [(2, 2), (1, 1), (3, 3), (4, 8)])
def test_gives_number_of_beautiful_arrangements(input, expected):
assert s.countArrangement(input) == expected
```

## My Solution

```
def check(n: int, index: int, checking: dict) -> int:
if index == 0:
return 1
total = 0
for i in range(1, n + 1):
if (i not in checking or not checking[i]) and (i % index == 0 or index % i == 0):
checking[i] = True
total += check(n, index - 1, checking)
checking[i] = False
return total
class Solution:
def countArrangement(self, n: int) -> int:
checking = {}
return check(n, n, checking)
```

## Analysis

## My Commentary

This is down as "medium" difficulty but I did find this pretty tricky. My solution could be a lot better but it's the best I was able to manage in the time I had.

I decided early on I'd need to do 2 things. I would have to iterate over the "list" and I would have to check each number against each index.

I decided to make a map of the number `1 to n`

and recursively check each number, setting a flag in a map to help skip that number in the recursive calls.

So the idea is, starting at 1, check every number in the list to see if they fulfil the requirement:

`perm[i]`

is divisible by`i`

.`i`

is divisible by`perm[i]`

.

We set the index to `n`

and decrement it in each recursive call to `check`

on the number `n`

. So each number `n`

recursively checks against every index. Now we get a count of each time the requirements are fulfilled for a number and index all the way down to the last index. This gives us a running count of all the valid **Beautiful Arrangemnts**.

## Top comments (0)