DEV Community

Ruairí O'Brien
Ruairí O'Brien

Posted on

1

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
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: n = 1
Output: 1
Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

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)

Enter fullscreen mode Exit fullscreen mode

Analysis

Alt Text

Alt Text

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.

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (0)

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up