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.