Beautiful Arrangement Count

Count permutations of 1..n where each position i satisfies divisibility with the number placed there.

recursion backtracking permutations counting

A beautiful arrangement is a permutation of integers from 1 to n such that for every index i (1-indexed), at least one of the following holds:
- The number at position i is divisible by i.
- i is divisible by the number at position i.

Given an integer n, write a function `count_arrangements(n)` that returns the number of beautiful arrangements for that n.

You must implement the function `count_arrangements(n: int) -> int`.

Constraints

1 <= n <= 15. The result fits within a 32-bit signed integer. Your solution should be efficient enough for n=15 (recursion with pruning is expected).

Example

>>> count_arrangements(1)
1
>>> count_arrangements(2)
2
>>> count_arrangements(3)
3

30 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use backtracking: place numbers 1..n one by one into positions 1..n.

At position pos, try only numbers that satisfy the divisibility condition with pos and are not yet used.

Track used numbers with a boolean list to avoid permutations.

Stop early if no valid number can be placed at a position.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.