## DEV Community is a community of 870,143 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Day 3 - Beautiful Arrangement

## The Problem

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 the beautiful arrangements that you can construct.

Example: 1

``````Input: n = 2
Output: 2
Explanation:
The first beautiful arrangement is [1,2]:
- perm = 1 is divisible by i = 1
- perm = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
- perm = 2 is divisible by i = 1
- i = 2 is divisible by perm = 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

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.