LeetCode 526: Beautiful Arrangement

Problem Restatement

We are given an integer n.

There are n integers labeled from 1 to n.

We need to count how many permutations of these numbers are beautiful.

A permutation perm is beautiful if, for every position i, at least one of these is true:

perm[i] % i == 0

or:

i % perm[i] == 0

The permutation is 1-indexed. That means positions start from 1, not 0.

The problem asks us to return the number of beautiful arrangements.

Input and Output

Example function shape:

def countArrangement(n: int) -> int:
    ...

Examples

For:

n = 2

The numbers are:

[1, 2]

There are two permutations.

First:

[1, 2]

At position 1, we have 1.

1 % 1 == 0

At position 2, we have 2.

2 % 2 == 0

So [1, 2] is beautiful.

Second:

[2, 1]

At position 1, we have 2.

2 % 1 == 0

At position 2, we have 1.

2 % 1 == 0

So [2, 1] is also beautiful.

Therefore:

countArrangement(2) == 2

For:

n = 1

There is only one permutation:

[1]

It is beautiful, so the answer is:

1

First Thought: Brute Force

The direct solution is to generate every permutation of the numbers from 1 to n.

For each permutation, check every position.

If every position satisfies the divisibility rule, count it.

Pseudo-code:

answer = 0

for perm in all_permutations([1, 2, ..., n]):
    valid = True

    for i in range(1, n + 1):
        if perm[i] % i != 0 and i % perm[i] != 0:
            valid = False
            break

    if valid:
        answer += 1

This works logically, but it wastes time.

It builds many permutations that fail early. For example, if position 2 already has a number that does not satisfy the rule, there is no reason to finish constructing the rest of that permutation.

Problem With Brute Force

There are n! permutations.

When n = 15, 15! is too large to enumerate directly.

So instead of generating all permutations and checking them later, we should build only valid partial arrangements.

This is a natural backtracking problem.

Key Insight

At position pos, we only need to try numbers num that satisfy:

num % pos == 0 or pos % num == 0

If a number does not satisfy this rule at the current position, placing it there can never lead to a valid arrangement.

So we prune that branch immediately.

The recursive idea is:

1. Fill position 1.
2. Then fill position 2.
3. Continue until position n.
4. Count one arrangement when all positions are filled.

We also need to remember which numbers have already been used.

Algorithm

Use a recursive backtracking function:

dfs(pos)

where pos is the current 1-indexed position we are trying to fill.

Maintain a boolean array:

used[num]

where used[num] tells us whether num has already been placed in the arrangement.

At each position:

1. Try every number from 1 to n.
2. Skip numbers that are already used.
3. Check whether the number satisfies the divisibility rule.
4. If valid, mark it as used.
5. Recurse to the next position.
6. Unmark it after recursion.

When pos == n + 1, all positions have been filled, so we found one beautiful arrangement.

Correctness

The algorithm tries to fill positions from 1 to n.

At every position pos, it only places a number num if num has not been used before. Therefore, every completed arrangement uses each number at most once.

Since the algorithm places exactly one number at each of the n positions, every completed arrangement uses exactly n numbers. Because all numbers come from 1 to n and no number is reused, every completed arrangement is a permutation of 1 through n.

The algorithm also checks the divisibility condition before placing a number. Therefore, every number placed at position pos satisfies:

num % pos == 0 or pos % num == 0

So every completed arrangement counted by the algorithm is beautiful.

Now consider any valid beautiful arrangement. At position 1, the algorithm will consider the number used by that arrangement. It passes the divisibility rule, so the recursion can choose it. The same is true for position 2, then position 3, and so on. Therefore, the algorithm has one recursive path that constructs this exact arrangement.

Thus, the algorithm counts every beautiful arrangement once and only once.

Complexity

The pruning makes the search much faster in practice than generating every permutation blindly.

The constraint n <= 15 is small enough for this backtracking approach.

Implementation

class Solution:
    def countArrangement(self, n: int) -> int:
        used = [False] * (n + 1)

        def dfs(pos: int) -> int:
            if pos == n + 1:
                return 1

            count = 0

            for num in range(1, n + 1):
                if used[num]:
                    continue

                if num % pos == 0 or pos % num == 0:
                    used[num] = True
                    count += dfs(pos + 1)
                    used[num] = False

            return count

        return dfs(1)

Code Explanation

We create a used array:

used = [False] * (n + 1)

The array has size n + 1 so that we can use numbers directly as indices.

For example, used[3] tells us whether number 3 has already been placed.

The recursive function is:

def dfs(pos: int) -> int:

It returns the number of valid arrangements that can be formed starting from position pos.

The base case is:

if pos == n + 1:
    return 1

If pos is n + 1, then positions 1 through n have already been filled. That means we found one complete beautiful arrangement.

Then we try every possible number:

for num in range(1, n + 1):

If the number is already used, we skip it:

if used[num]:
    continue

Otherwise, we check whether this number can be placed at the current position:

if num % pos == 0 or pos % num == 0:

If it can, we mark it as used:

used[num] = True

Then we count all arrangements that continue from the next position:

count += dfs(pos + 1)

After the recursive call, we undo the choice:

used[num] = False

This is the backtracking step. It allows the same number to be used in a different branch of the search.

Finally, we return the total count.

Testing

def run_tests():
    s = Solution()

    assert s.countArrangement(1) == 1
    assert s.countArrangement(2) == 2
    assert s.countArrangement(3) == 3
    assert s.countArrangement(4) == 8
    assert s.countArrangement(5) == 10

    print("all tests passed")

run_tests()

Test meaning: