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] = 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.